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
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 Output
For each of the
m lines, output a list of the most commonly used words starting with the corresponding user-entered word prefix 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