प्रिफिक्स (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 नाम ही दिखाएँ।

उदाहरण