题目描述

没头脑和不高兴正在玩文字游戏。没头脑说了一个字母，而不高兴说了一个以该字母开头的单词。但是这个词需要出现在给出的单词列表中，并且是相同首字母中使用的次数最少的单词。如果单词的选择不明确(即相同首字母中使用的次数最少的单词不止一个)，那么不高兴会选择字典序较小的单词。输入保证对于每个没头脑说出的字母，都有可以选择的单词。

假设有一个由 $K$ 个不同的单词组成的列表和一个没头脑给出的N个字母组成的列表。编写一个程序，根据输入，输出不高兴在游戏过程中说出的 $N$ 个单词。

输入格式

第一行输入包含来自的正整数 $K$ 和 $N$。 以下 $K$ 行是 $K$ 个单词，由小写英文字母组成，不超过 $21$ 个字母。 以下 $N$ 行是没头脑说的 $N$ 个小写英文字母。

输出格式

$N$ 行，分别对应 $N$ 个没头脑的询问。

样例

样例输入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

数据范围

• 对于$60$％的数据， $1 \leq K \leq 500，1 \leq N \leq 500$。
• 对于$100$%的数据，$1 \leq K \leq 100000，1 \leq N \leq 100000$。

大样例下载

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载