Word Suggestion

You are developing a text editor with a word suggestion feature. The goal is to provide users with a list of commonly used words based on the letters they have already typed. Your task is to implement this word suggestion feature using a given dataset of words and their frequencies.
You are provided with a collection of words and the number they were used in a text. For a given user-entered word prefix, you need to generate a list of up to 10 words that start with the prefix and have the highest encounter frequencies. The words should be sorted in descending order of encounter frequencies. If there are words with equal frequencies, sort them lexicographically. If there are more than ten different words starting with the given prefix, output only the first ten.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 10 000), representing the number of words found in the texts. Each of the following n lines contains a word and an integer separated by a space, where is a nonempty sequence of lowercase Latin letters with a length of at most 15 characters, and () is the number of times this word is encountered in the texts.
The next line contains an integer m (1 ≤ m ≤ 5000), representing the number of user-entered word prefixes. Each of the next m lines contains a word (a nonempty sequence of lowercase Latin letters with a length of at most 15 characters), which is the beginning of a word entered by a user.

Output

For each of the m lines, output a list of the most commonly used words starting with the corresponding user-entered word prefix . The words should be listed in descending order of encounter frequency. If there are words with equal frequencies, sort them lexicographically. If there are more than ten different words starting with the given prefix, output only the first 10 words.

Examples

Input
Output
6 fire 2 walk 2 with 2 me 2 fierce 1 win 3 3 fi w wi
fire fierce win walk with win with

Constraints

Time limit: 6 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue