配点 : $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)$ は英小文字からなります。 これらの名前を、高橋君の定めたアルファベット順に基づく辞書順に従って並べ替えてください。

制約

• $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$ 番目に小さいものを出力すること。

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

bzz
bzy
abx
caa

高橋君が新たに設定したアルファベット順において、b は a より小さく、z は y より小さいです。そのため、国民の名前を辞書順に並べ替えると、小さい順に bzz $,$ bzy $,$ abx $,$ caa となります。

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

b
a
ac
ab
abc