• Подстановочный шифр
  SUBSTITUTION CIPHER

Input file: cipher.in
Output file: cipher.out

Substitution ciphers were very much en vogue for the better part of the first millennium. A substitution cipher is a simple encryption method that encodes a given plain text by exchanging each letter with another letter. Julius Caesar, for example, used to replace each letter in a message with the letter that is three places further down the alphabet. Obviously, such a basic scheme is very easy to break.

However, by using an arbitrary rearrangement of the alphabet, it becomes much harder to break into a code. In fact, the gigantic number of possible rearrangements (26!>400.000.000.000.000.000.000.000.000) persuaded many ancient scholars to believe that the substitution cipher is unbreakable.

It took the inspiring era of the Abbasid caliphate and the genius of the ninth-century scientist Abu Yusuf Ya'quy ibn Is-haq ibn as-Sahhab ibn 'Omran ibn Ismail al-Kindi from Baghdad to come up with a general method to break any substitution cipher. His revolutionary new system of cryptoanalysis exploited the characteristic frequency of letters in a given language to reveal the original message.

Using a completely different approach and the help of modern computers, any substitution cipher can be deciphered today in no time. All that is needed is a dictionary of the language of the original message and the encoded message itself. Your task is to write such a program that automatically decodes any given encoded message.

Input Format
The first line of the input contains the encoded message. The encoded message will only contain lower-case letters and but the 26 letters of the English alphabet. A full stop (.) marks the end of the message.

The second line contains the number n of words in the dictionary. The following n lines contain the dictionary, with one word in each line. The dictionary appears in alphabetical order, and its entries are all lower-case words consisting only of the 26 letters of the English alphabet, too. Note, however, that the language is not necessarily English. The original message contains only words from the dictionary.

The maximal length of the encoded message is 1500 letters, and the dictionary will contain no more than 1500 entries.

Output Format
Your program needs to output the original plaintext message. There will be exactly one solution to each input file.

Example:

Sample Input
butwc fo butowc ljfwc o guyiukjmowc.
90
ako
bog
bosna
ce
ceznjiva
dim
do
domovina
drine
drugovi
ferije
fotografije
gde
gdje
gimnazijski
hej
hercegovina
i
iz
izblijedile
je
jedina
jedna
klikeri
krila
kunem
lahkih
leteci
letjet
mi
moja
moji
mojih
mora
mozes
na
nama
nek
nemamo
nista
nova
od
odred
oni
osim
osvajanju
periferije
pisma
pokoljenja
pola
poletjeti
pradjedova
prve
puta
s
sa
sacuva
sad
sam
samo
save
se
sestog
si
sminkeri
smo
snova
studentske
su
sve
sveske
svi
te
ti
tisucljetna
trebate
tresnje
tu
u
une
vec
vi
vidite
visina
vjernost
vremena
za
zelis
zemljo
zenice

Sample Output
jedna si jedina bosna i hercegovina.

Remarks
One possible letter substitution that leads to the sample output looks as follows: