Longest Common Suffix Queries
(रैप बैटल)
आपको
n अलग-अलग शब्दों की एक सूची दी गई है: , और q प्रश्न-शब्दों की एक सूची दी गई है। आपका काम प्रत्येक प्रश्न-शब्द w के लिए उस शब्द को ढूँढ़ना है, जो इस सूची a में मौजूद हो, w से अलग हो, और उसके साथ संयुक्त रूप से सबसे लंबा सuffix साझा करता हो। इन सब में से, आपको शब्दकोश क्रम में सबसे छोटे (lexicographically smallest) ऐसे शब्द को चुनना है।इनपुट
पहली पंक्ति में एकमात्र पूर्णांक
n दिया हुआ है (2 ≤ n ≤ 25 000), जो सूची में मौजूद शब्दों की संख्या दर्शाता है।अगली
n पंक्तियों में ये शब्द दिए होते हैं। प्रत्येक शब्द अंग्रेज़ी के छोटे अक्षरों से बना होता है और इसकी लंबाई 30 वर्णों से अधिक नहीं होती।इसके बाद की पंक्ति में एकमात्र पूर्णांक
q (1 ≤ q ≤ 25 000) दिया जाता है, जो प्रश्न-शब्दों की संख्या बताता है।अगली
q पंक्तियों में प्रश्न-शब्द दिए होते हैं।प्रत्येक प्रश्न-शब्द अंग्रेज़ी के छोटे अक्षरों से बना होता है और इसकी लंबाई 30 वर्णों से अधिक नहीं होती।
आउटपुट
प्रत्येक प्रश्न-शब्द के लिए एक पंक्ति में उस शब्द को छापें, जो सूची में मौजूद हो, प्रश्न-शब्द से भिन्न हो, उसके साथ सबसे लंबा सामान्य सuffix साझा करता हो, और शब्दकोश क्रम में सबसे छोटा हो।
उदाहरण
इनपुट | आउटपुट |
4
perfect
rhyme
crime
time
2
crime
rhyme | time
crime |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB