CF499B.Lecture

You have a new professor of graph theory and he speaks very quickly. You come up with the following plan to keep up with his lecture and make notes.

You know two languages, and the professor is giving the lecture in the first one. The words in both languages consist of lowercase English characters, each language consists of several words. For each language, all words are distinct, i.e. they are spelled differently. Moreover, the words of these languages have a one-to-one correspondence, that is, for each word in each language, there exists exactly one word in the other language having has the same meaning.

You can write down every word the professor says in either the first language or the second language. Of course, during the lecture you write down each word in the language in which the word is shorter. In case of equal lengths of the corresponding words you prefer the word of the first language.

You are given the text of the lecture the professor is going to read. Find out how the lecture will be recorded in your notes.

你新来了一位图论教授，他讲课语速非常快。为了跟上他的授课节奏并做好笔记，你想出了如下计划。

你掌握两种语言，而教授正用第一种语言授课。两种语言中的单词均由小写英文字母组成，每种语言都包含若干个单词。对于每种语言，所有单词互不相同（即拼写各不相同）。此外，这两种语言的单词之间存在一一对应关系：即对任一语言中的每个单词，另一语言中恰好存在一个具有相同含义的单词。

你可以将教授说的每个单词记录为第一种语言或第二种语言的形式。当然，在听课过程中，你会选择长度更短的那种语言来记录每个单词；若对应单词长度相等，则优先选用第一种语言的单词。

现给出教授即将讲授的 lecture 文本，请确定你的笔记中最终会如何记录该 lecture。

The first line contains two integers, n and m (1 ≤ n ≤ 3000, 1 ≤ m ≤ 3000) — the number of words in the professor's lecture and the number of words in each of these languages.

The following m lines contain the words. The i-th line contains two strings a__i, b__i meaning that the word a__i belongs to the first language, the word b__i belongs to the second language, and these two words have the same meaning. It is guaranteed that no word occurs in both languages, and each word occurs in its language exactly once.

The next line contains n space-separated strings _c_1, _c_2, ..., c__n — the text of the lecture. It is guaranteed that each of the strings c__i belongs to the set of strings {_a_1, _a_2, ... a__m}.

All the strings in the input are non-empty, each consisting of no more than 10 lowercase English letters.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 3000$，$1 \leq m \leq 3000$）——分别表示教授讲座中单词的总数，以及每种语言中单词的总数。

接下来的 $m$ 行描述这些单词。第 $i$ 行包含两个字符串 $a_i$、$b_i$，表示单词 $a_i$ 属于第一种语言，单词 $b_i$ 属于第二种语言，且这两个单词含义相同。保证没有任何单词同时出现在两种语言中，且每个单词在其所属语言中恰好出现一次。

下一行包含 $n$ 个以空格分隔的字符串 $c_1,\ c_2,\ \dots,\ c_n$ —— 即讲座的文本内容。保证每个字符串 $c_i$ 均属于集合 $\{a_1,\ a_2,\ \dots,\ a_m\}$。

输入中的所有字符串均非空，且每个字符串仅由至多 10 个小写英文字母组成。

Output exactly n words: how you will record the lecture in your notebook. Output the words of the lecture in the same order as in the input.

输出恰好 n 个单词：即你在笔记本中记录讲座内容的方式。按输入中的相同顺序输出讲座的各个单词。