प्रिफिक्स (Prefix) आधारित डेटाबेस
शुरुआत में आपके पास एक खाली डेटाबेस है, और आपको कई क्वेरीज़ को संभालना होगा। क्वेरी दो प्रकार की होती हैं: "Add" और "Search"। "Add" क्वेरी डेटाबेस में एक नाम जोड़ती है, जबकि "Search" क्वेरी के ज़रिए आपको उन सभी नामों को आउटपुट करना होता है जो दिए गए प्रिफिक्स से शुरू होते हैं, और ये नाम शब्दकोश क्रम (lexicographical order) में होने चाहिए। लेकिन यदि किसी प्रिफिक्स से मेल खाने वाले नाम 20 से ज़्यादा हों, तो केवल पहले 20 नाम ही दिखाने की आवश्यकता है।
इनपुट
इनपुट की पहली पंक्ति में पूर्णांक
q (1 ≤ q ≤ 200000) होता है, जो कुल क्वेरीज़ की संख्या बताता है। अगली q पंक्तियों में क्वेरीज़ निम्न प्रारूप में दी जाती हैं:- "Add" क्वेरी के लिए:
add s(यहाँsवह नाम है जिसे डेटाबेस में जोड़ा जाना है)।
- "Search" क्वेरी के लिए:
search p(यहाँpवह प्रिफिक्स है जिसकी खोज की जानी है)।
किसी भी क्वेरी स्ट्रिंग की लंबाई 20 से अधिक नहीं होगी।
आउटपुट
प्रत्येक "Search" क्वेरी के लिए, उन सभी नामों को स्पेस से अलग करके प्रिंट करें जो दिए गए प्रिफिक्स से शुरू होते हैं। यदि ऐसे नाम 20 से ज़्यादा हों, तो केवल पहले 20 नाम ही दिखाएँ।
उदाहरण
इनपुट | आउटपुट |
9
add cat
add code
add core
search co
add profound
add found
search fo
add fight
search f | code
core
found
fight
found |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 15 MB