Բառերի առաջարկում
Դուք մշակում եք տեքստային խմբագրիչ, որը պետք է ունենա բառերի առաջարկման հնարավորություն։ Նպատակն այն է, որ օգտատերերին տրամադրվի ամենահաճախ օգտագործվող բառերի ցանկ՝ հիմնված նրանց արդեն հավաքած տառերի վրա։ Ձեր անելիքն է իրագործել այդ բառերի առաջարկման համակարգը՝ օգտագործելով ձեզ տրամադրված բառերի հավաքածուն և դրանց հանդիպման հաճախականությունները։
Ձեզ տրված է բառերի մի ցանկ և այն հաճախականությունները, թե քանի անգամ են այդ բառերը հանդիպել տեքստում։ Յուրաքանչյուր օգտատիրոջ ներմուծած բառի նախաբանի (prefix) հիման վրա անհրաժեշտ է վերադարձնել առավելագույնը 10 բառ, որոնք սկսվում են այդ նախաբանից և ունեն հանդիպման ամենաբարձր հաճախականությունը։ Այդ բառերը պետք է դասավորվեն ըստ հանդիպման հաճախականության՝ նվազման կարգով, իսկ հավասար հաճախականության դեպքում՝ ըստ այբենական կարգի։ Եթե որևէ նախաբանի համար գտնված տարբերակների քանակը գերազանցում է տասը, պետք է վերադարձնել միայն առաջին տասը։
Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ 10 000), որը ներկայացնում է տեքստերում հայտնաբերված բառերի քանակը։Յուրաքանչյուր հաջորդ
n տողում գրված է w_i բառը և n_i ամբողջ թիվը՝ բաժանված բացատով, որտեղ w_i-ն լատինական փոքրատառերից կազմված ոչ դատարկ տող է (երկարությունը առավելագույնը 15 նիշ), իսկ n_i (1 ≤ n_i ≤ 10^6) ներկայացնում է տվյալ բառի հայտնվելու քանակը տեքստերում։Ելք
Յուրաքանչյուր
m տողի համար պետք է տպել մինչև 10 ամենահաճախ հանդիպող բառերը, որոնք սկսվում են տվյալ նախաբանից։ Բառերը պետք է ցուցադրվեն ըստ հանդիպման հաճախականության՝ նվազման կարգով, իսկ եթե հանդիպման քանակները հավասար են, ապա այբենական կարգով։ Եթե տարբերակները մեծ են տասից, պետք է արտածել միայն առաջին 10-ը։Օրինակներ
Input | Input |
6
fire 2
walk 2
with 2
me 2
fierce 1
win 3
3
fi
w
wi | 6
fire 2
walk 2
with 2
me 2
fierce 1
win 3
3
fi
w
wi |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB