有时，在将维基百科（Wikipedia）中的文本复制到论文中时，文本可能会被查重软件检测到。为了避免这种情况，必须先用自己的话重写文本，以免被软件标记。有很多方法可以做到这一点，其中之一是将文本通过翻译程序翻译成另一种语言，然后再翻译回来。如果你运气不好，尽管这样做了，翻译回来的文本可能仍然与原文过于相似。

你可以通过确保在有其他可能性的情况下，一个单词永远不会被翻译回它本身，来避免这个问题。形式化地，假设我们有一个包含 $N$ 个单词对 $(a, b)$ 的词典，其中 $a$ 是瑞典语单词，$b$ 是另一种语言的单词。如果对于某个单词 $z$，词典中存在两个单词对 $(x, z)$ 和 $(y, z)$，那么单词 $x$ 就可以被替换为单词 $y$。

给定一段文本，通过将单词翻译成另一种语言再翻译回来的方式，替换尽可能多的单词来重写它。

输入格式

第一行包含整数 $N$（$1 \le N \le 5000$），表示词典中的单词对数量。

接下来的 $N$ 行，每行包含一个单词对，首先是瑞典语单词，然后是另一种语言的单词。同一个单词绝不会同时出现在两种语言中，且没有单词对会重复出现。

接下来是一个整数 $M$（$1 \le M \le 1000$），表示文本中的单词数量。下一行包含 $M$ 个单词，即你需要翻译的文本。所有单词在词典中都至少作为瑞典语单词出现过一次。

所有单词的长度都在 $1$ 到 $20$ 个字母之间，且仅由 a-z 的字母组成。不保证这些单词是实际存在的真实单词。

输出格式

在单行中输出 $M$ 个单词，表示使用题目中描述的过程，将尽可能多的单词替换为同义词后的文本。如果一个单词有多个可能的同义词，你可以选择其中任意一个，只要它不是原单词即可。

样例

输入 1

4
skum foam
skum shady
fradga foam
typ type
2
skum typ

输出 1

fradga typ

说明 1

“skum” 有两个翻译，分别是 “foam” 和 “shady”。它们又可以被翻译回两个不同的单词：“skum” 和 “fradga”。为了避免将该单词翻译回 “skum”，你必须选择 “fradga”。

然而，对于第二个单词，只有一个可用的翻译，因此我们只能将其翻译回原单词。

输入 2

3
skum foam
skum shady
fradga foam
2
skum fradga

输出 2

fradga skum

子任务

你的解法将在若干个测试组上进行测试，每个测试组对应一定的分数。每个测试组包含一组测试用例。要获得一个测试组的分数，你需要通过该测试组中的所有测试用例。