URI Online Judge | 2852

Messaging

By Jessica Dagostini, URI Online Judge BR Brazil

Timelimit: 1

João and Enzo love encrypt their messages. To do this encrypt, they use the Vigènere cipher. This technique is really similar to the Cesar cipher, however its use a specific key for each letter in a word to be encrypted. The below table shows the ciphering pattern, that consists of the repetition of the alphabet 26 times, one time per row of this table, and in each row, the letters are displaced one space left. This 26 rows correspond to the 26 Cesar ciphers.

A random word is chosen as the keyword and each letter of this word indicates a line of the table to use to cipher or decipher the encrypted message. For example:

Once that do the encryption of all words in a message is a hard work, João and Enzo chosen to encrypt only words that initiate with a consonant letter. For this reason, they just apply the keyword on the words that they want to encrypt.

Given a keyword and a text message, your task is to encrypt this message with Vigènere cipher according to the João and Enzo added rule.

Input

The first line of the input consists of a keyword K (3 ≤ K ≤ 45), that represents the key to the cipher. This word is just composed by the alphabet (a-z) in lowercase, without spaces. The next line contains an integer N (1 ≤ N ≤ 150) that indicates how many messages we need to encrypt. The next N lines are the messages. These messages do not pass 105 characters and they are composed by the alphabet (a-z) in lowercase and by spaces.

Output

The output should display the encrypted message according to the friends rule.

Input Samples Output Samples
obi
2
olimpiada brasileira de informatica
ciencia da computacao
olimpiada psigjtsjzo em informatica
qjmbdqo ei qpudvbodic
informatica
2
ciencia da computacao
olimpiada brasileira de informatica
kvjbtua wi eouczhroah
olimpiada jefgzxebzc dm informatica