新字典序

题目描述

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

新的字母顺序由一个字符串 $X$ 表示，$X$ 是 a、b、$\ldots$、z 的一个排列。$X$ 的第 $i$ 个字符（$1 \le i \le 26$）是新顺序下第 $i$ 小的英文小写字母。

王国中有 $N$ 个公民，他们的名字是 $S_1, S_2, \dots, S_N$，每个 $S_i$（$1 \le i \le N$）由小写英文字母组成。

按照高桥君决定的字母顺序，将这些名字按字典序排序。

什么是字典序？简单来说，字典序就是单词在词典中列出的顺序。更正式的定义如下。下面给出判断两个不同字符串 $S$ 和 $T$ 之间字典序大小的算法。

下面用 $S_i$ 表示 $S$ 的第 $i$ 个字符。另外，若 $S$ 在字典序上小于 $T$，记为 $S \lt T$；若 $S$ 在字典序上大于 $T$，记为 $S \gt T$。

设 $L$ 为 $S$ 和 $T$ 长度中较小的一个。对于每个 $i=1,2,\dots,L$，检查 $S_i$ 和 $T_i$ 是否相同。

如果存在 $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$ 并结束。

如果不存在 $i$ 使得 $S_i \neq T_i$，则比较 $S$ 和 $T$ 的长度。若 $S$ 比 $T$ 短，则判定 $S \lt T$ 并结束；若 $S$ 比 $T$ 长，则判定 $S \gt T$ 并结束。

输入格式

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

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

输出格式

输出 $N$ 行。第 $i$ 行（$1 \le i \le N$）应输出按高桥君决定的字母顺序排序后第 $i$ 小的名字。

样例

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

bzz
bzy
abx
caa

在高桥君设定的新字母顺序中，b 小于 a，z 小于 y。因此，按字典序对这些公民的名字排序，从小到大依次为 bzz、bzy、abx、caa。

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

b
a
ac
ab
abc

数据范围

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