Alice and Bob text each other everyday. Bob, tired of writing long messages has come up with a way to reduce their size. Alice and Bob are both fluent in 2 languages, L1 and L2. A language consists of a collection of distinct words, where each word consists of lowercase letters in the english alphabet. Each word in L1 has a unique translation in L2 and vice versa. To reduce his effort, Bob writes his messages using words from both the languages such that the overall length of the message is minimum. In case the length of a word in both the languages is the same, then Bob writes the word in language L1.

Given the content of the message in language L1, find out how Bob will write the message using the above mentioned method.

Input:

The first line consists of n and m(1 <= n <= 3000, 1 <= m <= 3000) - the number of words in the message and the number of words in the language respectively.

Each word can be contain at most 10 lowercase letters in the english alphabet. It is guaranteed that no word occurs in both languages and each word occurs in its language exactly once.

The following m lines contain the words . The ith line contains 2 strings A[i] and B[i], where A[i] is in L1 and B[i] is in L2.

The next line contains n space separated strings from the language L1.

Output:

n space separated strings that form the message sent by Bob to Alice

Sample Input:

5 3

joll wuqrd

euzf un

hbnyiyc rsoqqveh

hbnyiyc joll joll euzf joll

Sample Output:

hbnyiyc joll joll un joll