管理 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)由小写英文字母组成。(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.  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.  3. 如果没有i比S_i \neq T_i早，我们比较S和T的长度。如果S比T短，我们判定S \lt T，然后放弃；如果S比T长，我们判定S \gt T，然后放弃。

输入内容由标准输入法提供，格式如下：

X

S1

S2

...

SN

打印 N 行。如果按照高桥决定的字母顺序对公民姓名进行排序，i（行）(1 \leq i \leq N)应该包含i（行）最小的姓名。

-   X 是一个顺序，重定过的 `a`, `b`, \ldots, `z`.

-   2 \leq N \leq 50000

-   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)