Auto-completion for Bessie’s Cell Phone

Bessie the cow now has a new cell phone and she loves sending text messages, though she often makes spelling errors. To help her overcome her typing difficulties, Farmer John has developed an auto-completion app.

The app is provided with a dictionary of \(W\) words, each consisting of lowercase letters (a to z). The sum of the lengths of all words does not exceed \(10^6\). Following the dictionary, the app then receives \(N\) queries. For the \(i\)th query, a partial word (prefix) and an integer \(K_i\) are given. The task is to determine the \(K_i\)th word in alphabetical order among those that start with the given prefix.

If there are fewer than \(K_i\) valid completions for a query, output NO RESULT.

For example, if the dictionary is ["app", "apple", "application"] and the query is prefix = "app" with \(K_i=2\), then after sorting the words the valid completions are ["app", "apple", "application"]. The answer is "apple".

inputFormat

The first line contains an integer \(W\) (the number of words in the dictionary).

The following \(W\) lines each contain a word (a non-empty string of lowercase letters).

The next line contains an integer \(N\) (the number of queries).

Each of the following \(N\) lines contains a query with a partial word (prefix) and an integer \(K_i\), separated by space.

outputFormat

For each query, output a single line containing the \(K_i\)th word in alphabetical order that starts with the given prefix. If there are fewer than \(K_i\) completions, output NO RESULT.

sample

3
app
apple
application
1
app 2

apple