Neo-lexicographic Ordering

题目描述

Takahashi，统治 AtCoder 王国，决定更改英文字母小写字母的字母顺序。 新的字母顺序由字符串 $X$ 表示，$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)$ 都由小写英文字母组成。
请根据 Takahashi 决定的字母顺序按字典序对这些名字进行排序。

输入格式

输入从标准输入以如下格式给出： $X$ $N$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

打印 $N$ 行。第 $i$ 行 $(1 \leq i \leq N)$ 应该包含按 Takahashi 决定的字母顺序排序后第 $i$ 小的名字。

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

bzz
bzy
abx
caa

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

b
a
ac
ab
abc

提示

$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)$在 Takahashi 设定的新字母顺序中，$b$ 小于 $a$ 且 $z$ 小于 $y$。因此，将公民的名字按字典序排序会得到按升序排列的 $bzz$, $bzy$, $abx$, $caa$。

标签: AtCoder|abc219C

来源

AtCoder|abc219C