Score : $300$ points

问题描述

Takahashi，治理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)$由小写英文字母组成。
按照Takahashi决定的字母顺序，对这些名字进行字典序排序。

什么是字典序？

简单来说，字典序就是词典中单词排列的顺序。更正式地讲，以下是确定不同字符串$S$和$T$之间的字典序的算法。

以下，用$S_i$表示字符串$S$的第$i$个字符。此外，如果$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. 如果不存在满足$S_i \neq T_i$的$i$，则比较$S$和$T$的长度。若$S$比$T$短，则确定$S \lt T$并停止比较；若$S$比$T$长，则确定$S \gt T$并停止比较。

按照Takahashi决定的新字母顺序，请按字典序对这$N$位公民的名字进行排序。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.

The new alphabetical order is represented by a string $X$, which is a permutation of a, b, $\ldots$, z. The $i$-th character of $X$ $(1 \leq i \leq 26)$ would be the $i$-th smallest English lowercase letter in the new order.

The kingdom has $N$ citizens, whose names are $S_1, S_2, \dots, S_N$, where each $S_i$ $(1 \leq i \leq N)$ consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings $S$ and $T$.

Below, let $S_i$ denote the $i$-th character of $S$. Also, if $S$ is lexicographically smaller than $T$, we will denote that fact as $S \lt T$; if $S$ is lexicographically larger than $T$, we will denote that fact as $S \gt T$.

1. Let $L$ be the smaller of the lengths of $S$ and $T$. For each $i=1,2,\dots,L$, we check whether $S_i$ and $T_i$ are the same.
2. If there is an $i$ such that $S_i \neq T_i$, let $j$ be the smallest such $i$. Then, we compare $S_j$ and $T_j$. If $S_j$ comes earlier than $T_j$ in alphabetical order, we determine that $S \lt T$ and quit; if $S_j$ comes later than $T_j$, we determine that $S \gt T$ and quit.
3. If there is no $i$ such that $S_i \neq T_i$, we compare the lengths of $S$ and $T$. If $S$ is shorter than $T$, we determine that $S \lt T$ and quit; if $S$ is longer than $T$, we determine that $S \gt T$ and quit.

Constraints

• $X$ is a permutation of a, b, $\ldots$, z.
• $2 \leq N \leq 50000$
• $N$ is an integer.
• $1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)$
• $S_i$ consists of lowercase English letters. $(1 \leq i \leq N)$
• $S_i \neq S_j$ $(1 \leq i \lt j \leq N)$

Input

Input is given from Standard Input in the following format:

$X$

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

Print $N$ lines. The $i$-th line $(1 \leq i \leq N)$ should contain the $i$-th smallest name when the citizens' names are sorted according to the alphabetical order decided by Takahashi.

Sample Input 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

Sample Output 1

bzz
bzy
abx
caa

In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.

Sample Input 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

Sample Output 2

b
a
ac
ab
abc

update @ 2024/3/10 09:41:18