ワードサジェスト機能
あなたは、単語サジェスト機能を備えたテキストエディタを開発しています。ユーザがすでに入力した文字列をもとに、よく使われる単語を候補として提示することを目的としています。与えられた単語とその出現頻度のデータセットを活用して、この単語サジェスト機能を実装してください。
与えられたのは、テキスト中に出現した単語の一覧と、それぞれが何回使用されたかを示す数です。ユーザが入力した単語の先頭部分（プレフィックス）を受け取り、そのプレフィックスで始まる単語のうち出現頻度が高い最大10個を求めます。単語は出現頻度の降順で並べ、頻度が同じ場合は辞書順（アルファベット順）でソートしてください。もし同じプレフィックスで始まる単語が10種類を超える場合は、上位10個のみを出力します。
入力
最初の行には、テキストに出現した単語の数を表す整数
n (1 ≤ n ≤ 10 000) が与えられます。続く n 行には、それぞれ単語 と整数 が空白区切りで与えられます。 は小文字のラテン文字からなる長さ最大15文字の文字列で、 (1 ≤ n_i ≤ 10^6) はテキスト中でこの単語が使用された回数を示します。次の行には、ユーザが入力した単語のプレフィックスの数を表す整数
m (1 ≤ m ≤ 5000) が与えられます。続く m 行のそれぞれに、ユーザが入力した単語の先頭部分 （小文字のラテン文字で最大15文字）が与えられます。出力
m 行の各プレフィックスについて、そのプレフィックスで始まる最も使用頻度が高い単語を最大で10個まで出力してください。単語は登場頻度の降順で並べ、同じ頻度の単語は辞書順でソートします。もし該当する単語が10個を超える場合は、最初の10単語のみを出力してください。例
入力 | 出力 |
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