AT_abc219_c [ABC219C] Neo-lexicographic Ordering

AtCoder 王国的统治者高桥君决定更改英文字母的字母顺序。 新的字母顺序由将 `a`、`b`、$\ldots$、`z` 重新排列得到的字符串 $X$ 表示。$X$ 的第 $i$ 个字符（$1 \leq i \leq 26$）表示在新的顺序中第 $i$ 小的英文字母。 AtCoder 王国有 $N$ 位国民，每位国民的名字分别为 $S_1, S_2, \dots, S_N$。其中，$S_i$（$1 \leq i \leq N$）由小写英文字母组成。 请根据高桥君制定的新字母顺序，对这些名字按字典序进行排序。 什么是字典序？字典序简单来说就是“单词在字典中出现的顺序”。更严格地说，判断由小写英文字母组成的不同字符串 $S$、$T$ 的大小关系的算法如下： 下面用 $S_i$ 表示 $S$ 的第 $i$ 个字符。当 $S$ 在字典序上小于 $T$ 时记作 $S < T$，大于时记作 $S > T$。 1. 设 $L$ 为 $S$ 和 $T$ 中较短的字符串的长度。对于 $i=1,2,\dots,L$，依次比较 $S_i$ 和 $T_i$ 是否相同。 2. 如果存在 $S_i \neq T_i$ 的 $i$，则取最小的这样的 $i$，记为 $j$。比较 $S_j$ 和 $T_j$，若 $S_j$ 在字母顺序上小于 $T_j$，则 $S < T$，否则 $S > T$，算法结束。 3. 如果不存在 $S_i \neq T_i$ 的 $i$，则比较 $S$ 和 $T$ 的长度，若 $S$ 比 $T$ 短，则 $S < T$，否则 $S > T$，算法结束。

输入按以下格式从标准输入读入。 > $X$ > $N$ > $S_1$ > $S_2$ > $\vdots$ > $S_N$

输出 $N$ 行。第 $i$ 行输出按高桥君指定的新字母顺序排序后，第 $i$ 小的国民名字。

### 限制条件 - $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 < j \leq N$） ### 样例解释 1 在高桥君新设定的字母顺序中，`b` 比 `a` 小，`z` 比 `y` 小。因此，按字典序排序后，国民的名字依次为 `bzz`、`bzy`、`abx`、`caa`。 由 ChatGPT 4.1 翻译