হাসিনুর চট্টগ্রামের ‘X স্কুল অ্যান্ড কলেজে’ পড়ে। তার স্কুলের সবচেয়ে রাগী এবং কড়া শিক্ষক হলো AA স্যার। তার নামে কথিত আছে তিনি অমানষিক শাস্তি দিতে পারেন যতক্ষণ না ছাত্ররা সহ্য করতে পারে।
একদিন ক্লাসে কথা বলতে গিয়ে হাসিনুর AA স্যারের হাতে খুব বাজেভাবে ধরা খায়। AA স্যার তাকে কঠোর শাস্তি দেওয়ার ব্যাবস্থা করেন।
শাস্তির অংশ হিসেবে হাসিনুরকে একটি বই দেওয়া হয়। বইয়ের নাম ‘Art of prefix’। এই বইয়ে ‘n’ সংখ্যক শব্দ আছে। হাসিনুর তার শাস্তির অংশ হিসেবে একটি শব্দ ‘S’ পাবে। হাসিনুর কে এখন প্রদত্ত বই থেকে এমন শব্দ খুজে বের করতে হবে যেটার Prefix হিসেবে ‘S’ শব্দটি রয়েছে। এক্ষেত্রে, যদি অনেক গুলো শব্দ পাওয়া যায় তবে যেই শব্দ সবচেয়ে বেশীবার রয়েছে তা বের করতে হবে। এক্ষেত্রে, সলিউশন অনেকগুলো হলে যেটা Lexicographically Smallest, সেটি বের করতে হবে এবং পুরো বইয়ে কতোবার আছে তা বলতে হবে।
আর হ্যাঁ, হাসিনুরকে এই কাজটি q বার করতে হবে। অন্যথায় সে বাড়ি যেতে পারবেনা এবং শাস্তির পরিমাণও বেড়ে যেতে পারে।
প্রথম লাইনে n এর মান দেওয়া থাকবে, যা নির্দেশ করবে বইয়ে শব্দ সংখ্যা। পরের n লাইনে n টি শব্দ দেওয়া থাকবে।
এরপর আরেকটি মান ‘q’ দেওয়া থাকবে। এরপরের ‘q’ লাইনে q টি Prefix দেওয়া হবে। এবং প্রতিটির জন্য উত্তর দিতে হবে।
সীমাবদ্ধতাঃ
৩০ পয়েন্টের জন্যঃ
1 <= n <= 1000
1 <= q <= 1000
1 <= শব্দ দৈর্ঘ্য <= 10
১০০ পয়েন্টের জন্যঃ
1 <= n <= 500000
1 <= q <= 100000
1 <= শব্দ দৈর্ঘ্য <= 10
শব্দ গুলো সব ইংরেজী ভাষার ছোট অক্ষরে (a-z) দেওয়া থাকবে।
প্রতিটি প্রশ্নের জন্য প্রিন্ট করতে হবে ‘Case X: Y Z’।
যেখানে;
X = প্রশ্ন সংখ্যা।
Y = প্রশ্ন অনুযায়ী পাওয়া শব্দটি।
Z = কতবার শব্দটি বইয়ে আছে।
অথবা, ‘Case X: -1’. যদি প্রশ্ন আনুযায়ী কোন শব্দ বইয়ে খুজে না পাওয়া যায়।
Input | Output |
---|---|
10 tama pika nafu nasif nurul nobel moshi hashi moshiur moshiur 5 mos no na tama ha | Case 1: moshiur 2 Case 2: nobel 1 Case 3: nafu 1 Case 4: tama 1 Case 5: hashi 1 |