你们有一位新的图论教授,他说话很快。你想出了以下计划来跟上他的讲座并做笔记。
你懂两种语言,教授正在用第一种语言授课。两种语言中的单词均由小写英文字符组成,每种语言均由多个单词组成。对于每种语言,所有单词都是不同的,即它们的拼写不同。而且,这些语言的单词具有一一对应的关系,即每种语言中的每个单词,在另一种语言中恰好存在一个具有相同含义的单词。
您可以用第一语言或第二语言写下教授所说的每个单词。当然,在讲座期间,您可以用该单词较短的语言写下每个单词。如果相应单词的长度相同,您更喜欢第一语言的单词。
您将获得教授将要阅读的讲座文本。了解如何将讲座记录在您的笔记中。
输入
第一行包含两个整数,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