शब्द सुझाव
आप एक टेक्स्ट एडिटर विकसित कर रहे हैं जिसमें शब्द सुझाव (word suggestion) फ़ीचर शामिल है। इसका मुख्य उद्देश्य यह है कि उपयोगकर्ता द्वारा टाइप किए गए प्रारंभिक अक्षरों के आधार पर, उन्हें अक्सर उपयोग किए जाने वाले शब्दों की एक सूची प्रदान की जाए। आपकी ज़िम्मेदारी है कि आपको दिए गए शब्दों और उनकी आवृत्तियों (frequencies) के डेटा की सहायता से इस शब्द सुझाव फ़ीचर को लागू करना है।
आपको कई शब्दों का एक संग्रह दिया गया है, जिसमें प्रत्येक शब्द के साथ यह भी बताया गया है कि उसे लिखित सामग्रियों में कितनी बार इस्तेमाल किया गया। किसी भी उपयोगकर्ता द्वारा दर्ज किए गए शब्द-प्रीफ़िक्स (prefix) के लिए, आपको अधिकतम 10 शब्दों की एक सूची तैयार करनी होगी, जिनके प्रारंभिक अक्षर उस प्रीफ़िक्स से मेल खाते हों और जिनकी आवृत्तियाँ सबसे अधिक हों। आपको इन शब्दों को आवृत्ति के आधार पर अवरोही क्रम (descending order) में छाँटना है। यदि किसी शब्द की आवृत्ति समान हो, तो उन्हें शब्दकोशीय क्रम (lexicographical order) में व्यवस्थित करें। यदि किसी प्रीफ़िक्स से शुरू होने वाले 10 से ज़्यादा शब्द उपलब्ध हैं, तो केवल पहले 10 शब्द ही दिखाएँ।
इनपुट
इनपुट की पहली पंक्ति में एक पूर्णांक
n (1 ≤ n ≤ 10 000) होगा, जो बताता है कि कुल कितने शब्द मिले हैं।अगली
n पंक्तियों में से प्रत्येक में एक शब्द w_i और एक पूर्णांक n_i स्पेस के साथ दिया गया है, जहाँ w_i अधिकतम 15 अक्षरों तक का एक छोटा लोअरकेस लैटिन शब्द है, और n_i (1 ≤ n_i ≤ 10^6) वह संख्या है जो बताती है कि यह शब्द कितनी बार पाया गया।आउटपुट
हर एक प्रीफ़िक्स
u_i के लिए, आपको उन सबसे अधिक बार उपयोग में आने वाले शब्दों की सूची प्रिंट करनी है जो उस प्रीफ़िक्स से शुरू होते हैं। इन शब्दों को आवृत्ति के आधार पर घटते क्रम में दिखाएँ। यदि किसी शब्द की आवृत्ति एक जैसी हो, तो उन्हें शब्दकोशीय क्रम में रखें। अगर किसी प्रीफ़िक्स से शुरू होने वाले शब्द 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