← 返回题目列表

AtCoder · abc219_c

E. 新词典排序

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

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

新的字母顺序由字符串表示 X,这是一个排列 a, b, \ldots, z。的 i第一个字符 X (1 \leq i \leq 26) 将是 i- 新顺序中最小的英文小写字母。

王国有 N 公民,其姓名为 S_1, S_2, \dots, S_N,其中每个 S_i (1 \leq i \leq N) 由小写英文字母组成。
根据高桥决定的字母顺序对这些名字进行字典顺序排序。

字典顺序是什么?

简单来说,词典顺序就是单词在词典中列出的顺序。作为更正式的定义,这里是确定不同字符串之间的字典顺序的算法 S 和 T.

下面,让 S_i 表示 i第一个字符 S。另外,如果 S 按字典顺序小于 T,我们将该事实表示为 S \lt T;如果 S 按字典顺序大于 T,我们将该事实表示为 S \gt T.

  1. 让 L 是以下长度中较小的一个 S 和 T。对于每个 i=1,2,\dots,L,我们检查是否 S_i 和 T_i 是相同的。
  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. 如果没有 i 这样 S_i \neq T_i,我们比较长度 S 和 T。如果 S 短于 T,我们确定 S \lt T 然后退出;如果 S 长于 T,我们确定 S \gt T 然后退出。

约束

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

输入

输入由标准输入按以下格式给出:

X
N
S_1
S_2
\vdots
S_N

输出

打印 N 行。的 i第行 (1 \leq i \leq N) 应包含 i- 根据高桥决定的字母顺序对公民姓名进行排序时的最小名称。


示例输入 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

示例输出 1

bzz
bzy
abx
caa

按照高桥设定的新字母顺序, b 小于 a 和 z 小于 y。因此,按字典顺序对公民姓名进行排序将导致 bzz, bzy, abx, caa 按升序排列。


示例输入 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

示例输出 2

b
a
ac
ab
abc