EIU Programming Practices and Exams

Beo and his girlfriend are learning A and B languages, so when chatting, they often use words between these two languages. For each language, all words are different and each word in A has a unique word in language B. For each word (in A language), Beo will choose the shorter word in two languages. For example, if the word "tourist" in A is equivalent to "rng58" in B, then Beo will write "rng58". Note that if two words have the same length, Beo will write in A. Given the original paragraph Beo wants to send (int A language), output the paragraph that Beo will send to his girlfriend.

Input

The first line contains 2 numbers n and m, the number of words Beo wants to send and the number of words for each language

+ m the next line, each line contains 2 words - a word in language A and the corresponding word in language B.

+ The last line contains n words Beo wants to send to his girlfriend.

Output

+ Ouput the paragraph that Beo will send.

Example

Input:

5 3
joll wuqrd
euzf un
hbnyiyc rsoqqveh
hbnyiyc joll joll euzf joll

Output: 

hbnyiyc joll joll un joll