Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIUTRANS - Messages

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 - words in language A and corresponding words in language B.
+ The last line contains n words Beo wants to send to his girlfriend.

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


Added by:Ha Minh Ngoc
Date:2015-02-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NCSHARP GOSU JULIA PYPY3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.