问题陈述

高桥是 AtCoder 王国的统治者，他决定改变英文字母的小写字母顺序。

新的字母顺序用字符串 $X$ 表示，它是 a, b, $\\ldots$, z 的一个排列。$X$ 的第 $i$ 个字符 $(1 \\leq i \\leq 26)$ 是新顺序中第 $i$ 小的英文字母。

王国有 $N$ 名公民，他们的名字是 $S_1, S_2, \\dots, S_N$，其中每个 $S_i$ $(1 \\leq i \\leq N)$ 由小写英文字母组成。按照高桥决定的字母顺序将这些名字按词典顺序进行排序。

什么是词典顺序？

简单地说，词典顺序是单词在字典中列出的顺序。作为更正式的定义，下面是确定不同字符串 $S$ 和 $T$ 之间词典顺序的算法。

下面，我们将 $S_i$ 表示为 $S$ 的第 $i$ 个字符。此外，如果 $S$ 在词典顺序上小于 $T$，我们将把这个事实表示为 $S \\lt T$；如果 $S$ 在词典顺序上大于 $T$，我们将把这个事实表示为 $S \\gt T$。

1. 让 $L$ 是 $S$ 和 $T$ 的长度中较小的一个。对于每个 $i=1,2,\\dots,L$，我们检查 $S_i$ 和 $T_i$ 是否相同。
2. 如果存在 $i$，使得 $S_i \\neq T_i$，让 $j$ 是最小的这样的 $i$。然后，我们比较 $S_j$ 和 $T_j$。如果 $S_j$ 在字母顺序中出现在 $T_j$ 之前，我们确定 $S \\lt T$ 并且停止；如果 $S_j$ 在 $T_j$ 之后出现，我们确定 $S \\gt T$ 并且停止。
3. 如果不存在这样的 $i$，我们比较 $S$ 和 $T$ 的长度。如果 $S$ 比 $T$ 短，我们确定 $S \\lt T$ 并且停止；如果 $S$ 比 $T$ 长，我们确定 $S \\gt T$ 并且停止。

约束条件

• $X$ 是 a, b, $\\ldots$, z 的一个排列。
• $2 \\leq N \\leq 50000$
• $N$ 是一个整数。
• $1 \\leq |S_i| \\leq 10 \\, (1 \\leq i \\leq N)$
• $S_i$ 由小写英文字母组成。$(1 \\leq i \\leq N)$
• $S_i \\neq S_j$ $(1 \\leq i \\lt j \\leq N)$

输入

输入以以下格式从标准输入给出：

$X$ $N$ $S_1$ $S_2$ $\\vdots$ $S_N$

输出

打印 $N$ 行。第 $i$ 行 $(1 \\leq i \\leq N)$ 应包含按照高桥决定的字母顺序排序时公民姓名中的第 $i$ 小的名字。

示例输入 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

示例输出 1

bzz
bzy
abx
caa

根据高桥设定的新字母顺序，b 比 a 小，z 比 y 小。因此，按照词典顺序对公民姓名排序将得到升序排列的 bzz，bzy，abx，caa。

示例输入 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

示例输出 2

b
a
ac
ab
abc