← 返回题目列表

Codeforces · 499/B

B. 讲座

中文机器翻译题面 查看原题

你们有一位新的图论教授,他说话很快。你想出了以下计划来跟上他的讲座并做笔记。

你懂两种语言,教授正在用第一种语言授课。两种语言中的单词均由小写英文字符组成,每种语言均由多个单词组成。对于每种语言,所有单词都是不同的,即它们的拼写不同。而且,这些语言的单词具有一一对应的关系,即每种语言中的每个单词,在另一种语言中恰好存在一个具有相同含义的单词。

您可以用第一语言或第二语言写下教授所说的每个单词。当然,在讲座期间,您可以用该单词较短的语言写下每个单词。如果相应单词的长度相同,您更喜欢第一语言的单词。

您将获得教授将要阅读的讲座文本。了解如何将讲座记录在您的笔记中。

输入

第一行包含两个整数,n 和 m (1 ≤ n ≤ 3000, 1 ≤ m ≤ 3000) — 教授讲座中的字数以及每种语言的字数。

以下 m 行包含单词。第i行包含两个字符串ai,bi,表示单词ai属于第一语言,单词bi属于第二语言,这两个单词具有相同的含义。保证没有单词同时出现在两种语言中,并且每个单词在其语言中只出现一次。

下一行包含 n 个空格分隔的字符串 c1, c2, ..., cn — 讲座的文本。保证每个字符串 ci 属于字符串集合 {a1, a2, ... am}。

输入中的所有字符串均非空,每个字符串由不超过 10 个小写英文字母组成。

输出

准确输出 n 个单词:您将如何在笔记本中记录讲座。按照与输入相同的顺序输出讲座的单词。

示例

输入 #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