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.

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.

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

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.

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

b
a
ac
ab
abc