Zig 和 Zag 正在玩一个单词游戏。Zig 说一个字母，Zag 则说一个以该字母开头的单词。但是，该单词必须来自给定的候选单词列表，并且是 Zag 目前为止说过的次数最少的单词。如果存在多个候选单词说过的次数相同且最少，Zag 会选择其中字典序最小（在字母表中出现最靠前）的一个。保证对于 Zig 给出的每个字母，都一定能选出一个单词。

现在给定一个包含恰好 $K$ 个不同单词的列表，以及一个由 Zig 给出的 $N$ 个字母组成的序列。请编写一个程序，根据输入，输出 Zag 在游戏过程中说出的 $N$ 个单词。

输入格式

输入的第一行包含两个正整数 $K$（$1 \le K \le 100\,000$）和 $N$（$1 \le N \le 100\,000$）。

接下来的 $K$ 行，每行包含一个仅由小写英文字母组成的单词，长度不超过 21 个字符。

接下来的 $N$ 行，每行包含一个小写英文字母。

输出格式

输出共 $N$ 行，每行包含一个单词，即 Zag 说的单词。

子任务

对于 $60\%$ 的测试数据，满足 $N$ 和 $K$ 均小于 $500$。

样例

输入样例 1

4 5
zagreb
split
zadar
sisak
z
s
s
z
z

输出样例 1

zadar
sisak
split
zagreb
zadar

输入样例 2

5 3
london
rim
pariz
moskva
sarajevo
p
r
p

输出样例 2

pariz
rim
pariz

输入样例 3

1 3
zagreb
z
z
z

输出样例 3

zagreb
zagreb
zagreb