Problem G
Auto Completion

The auto completion algorithm works based on a pre-defined dictionary of $n$ words. Suppose the search box contains the text $w$. When the user presses the tab key $i$ times in a row, the algorithm finds the $i$-th lexicographically smallest word from the dictionary that has $w$ as its non-trivial prefix. If there are fewer than $i$ words that have $w$ as prefix, the algorithm circulates through these words. That is, if there are $j < i$ words that have $w$ as prefix, the $(j+1)$-th tab press goes back to the lexicographically smallest word, and the $(j+2)$-th tab press gives the second lexicographically smallest word, and so on. The chosen word then replaces the text in the search box. If there are no words that have $w$ as prefix, pressing the tab has no effect. When the user types a letter, the letter is directly appended to the text.

For example, suppose the dictionary has four words: “albert”, “app”, “apple”, and “appletree”. If the user types “app” and then presses the tab key twice, she will get “appletree”, which is the second lexicographically smallest word that has “app” as non-trivial prefix. If she presses the tab key three times instead after typing “app”, she will get “apple” by the word circulation design. The user may also obtain “appletree” by first typing “a”, pressing the tab key three times (getting “apple”), typing two letters “tr”, and finally pressing the tab key once.

You team has prepared some simulated user keystroke sequences for you to test the auto completion.

Input

The first line has a single integer $n$ ($1 \leq n \leq 10^5$), the number of words in the dictionary. Each of the next $n$ lines gives a dictionary word. All dictionary words are unique and contain only lowercase English letters. No dictionary word has a length larger than $10^5$. The total length of all dictionary words does not exceed $5 \cdot 10^5$.

The next line has a single integer $q$ ($1 \leq q \leq 10^5$), the number of keystroke sequences. Each of the next $q$ lines has a string that represents a user’s keystroke sequence. A keystroke sequence consists of lowercase English letters and hash signs. Each hash sign denotes one press on the tab key. The total length of all keystroke sequences does not exceed $5 \times 10^5$. No keystroke sequence starts with a hash sign. It is assumed that the user does not pause between two consecutive tab presses, so that a sequence of consecutive tab presses triggers the auto completion only once.

It is guaranteed that the total length of the text produced by all keystroke sequences does not exceed $10^6$.

Output

For each keystroke sequence, output the text it produces on a single line.

6
app
apple
appletree
albert
avoid
banana
11
a#
a##
a####
a#######
app#
applet#
a#####tle#
ab#andon
app#t#
b##s#
cat

albert
app
appletree
app
apple
appletree
avoidtle
abandon
appletree
bananas
cat