B. Emoji Master BSQ
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

As everyone knows, BSQ is an emoji master.

Now BSQ has given you the conversion rules of $$$n$$$ words. Please convert what BSQ said according to the rules.

Input

The first line contains two integer $$$n, m$$$ $$$(1 \le n, m \le 100)$$$.

Then $$$n$$$ lines follow, the $$$i$$$-th of them contains two strings $$$s_i$$$ and $$$t_i$$$ $$$(1 \le |s_i|, |t_i| \le 10)$$$ — This means that the word $$$s_i$$$ needs to be converted into the word $$$t_i$$$, it is guaranteed all $$$s_i$$$ and $$$t_i$$$ are distinct.

The next line contains $$$m$$$ words $$$p_1, p_2, ... , p_m$$$ $$$(1 \le |p_i| \le 10)$$$, separate with a space. — This is what BSQ said. It is guaranteed that for each integer $$$i$$$ $$$(1 \le i \le m)$$$, there exist an integer $$$j$$$ $$$(1 \le j \le n)$$$ satisfies $$$p_i = s_j$$$.

It is guaranteed that all words contain only lowercase English letters.

Output

Output one line contains $$$m$$$ words $$$q_1, q_2, ... , q_m$$$, separate with a space. — This represents the result after conversion.

Example
Input
3 4
wo i
qiu ball
ni you
wo qiu qiu ni
Output
i ball ball you