Lecture

题意翻译

### 题目描述 你现在有一位新图论教授,你觉得他讲课讲的很好,但他说话实在是太快了,搞得你根本没有时间记笔记。所以呢,你有一个计划来跟上他讲课时的“脚步”,并记下重要的笔记。 你总共会两种语言:A 语言和 B 语言,教授用来讲课的是其中的 A 语言。A 语言和 B 语言有以下共同点: - 它们都由若干小写字母构成; - 每个单词里都不包括空格; - 它们的长度都不超过 10。 另外,可以保证同一种语言中任意两个单词都有不同的拼写,且 A 语言的每一个单词与 B 语言中的每一个单词一一对应。 你的做笔记方式如下: - 你必须写出写出教授给出的每一个单词; - 为保证写单词用时最短,你必须要选择两种语言中单词长度更短的一个; - 如果两个单词的长度一样,为保证讲课的原汁原味,你会选择第一种语言来做笔记。 我们会给你教授的演讲。而你呢,需要编一个程序来写出你的笔记。 ### 输入格式 第一行包括两个整数,分别为教授的演讲里有多少个单词的 $n$,还有两种语言中共有多少词汇的 $m$($1 \leq n \leq 3\,000$,$1 \leq m \leq 3\,000$) 接下来有 $m$ 行,每行两个单词,分别为 $a_i$ 和 $b_i$(两种语言里的单词) 最后一样中有 $n$ 个单词,代表教授的演讲。 ### 输出格式 输出 $n$ 个单词,代表按照题目中的规则你记下的笔记。 感谢@deadpool123 提供的翻译

题目描述

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.

输入输出格式

输入格式


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.

输出格式


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.

输入输出样例

输入样例 #1

4 3
codeforces codesecrof
contest round
letter message
codeforces contest letter contest

输出样例 #1

codeforces round letter round

输入样例 #2

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

输出样例 #2

hbnyiyc joll joll un joll