/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
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 \lt T 、大きい場合は S \gt T と表します。
- S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、S_j が T_j よりアルファベット順で小さい場合は S \lt T 、そうでない場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、S と T の長さを比較して、S が T より短い場合は S \lt 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
Score : 300 points
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.
- 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.
- 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.
- 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