新字典序排序

题目描述

小高是 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)$ 由小写英文字母组成。

按照小高决定的字母顺序，对这些名字进行字典序排序

输入格式

第一行输入一个字符串 $X$。

第二行输入一个整数 $N$。

接下来有 $N$ 行，每行输入字符串 $S_i$。

输出格式

输出 $N$行。

第 $i\ \,\ (1\ \leq\ i\ \leq\ N)$ 行应包含按小高决定的字母顺序排序后的第 $i$ 小的名字

样例

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

bzz
bzy
abx
caa

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

b
a
ac
ab
abc

提示

样例说明 1

在小高设定的新字母顺序中，b 比 a 小，z 比 y 小。

因此，按字典序排序公民的名字会得到 bzz、bzy、abx、caa 的升序结果。

数据范围

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