Hide

Problem G
Auto Completion

/problems/autocompletion/file/statement/en/img-0001.png
You are creating an awesome web application for this year’s hackNY hackathon. Everything goes well except that the search box in your application (which is a native HTML input tag) appears a little clumsy given that the user always has to type everything from scratch. To improve the user experience, your team has decided to add an auto completion feature to the search box. However all other team members are busy. So you are asked to program the auto completion algorithm.

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.

Sample Input 1 Sample Output 1
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

Please log in to submit a solution to this problem

Log in