Hasinur studies at X School & College situated in Chittagong. AA Sir is one of the toughest and roughest teachers in his class. He has a reputation for giving painful punishment to his students as long as they can survive.
One day, Hasinur caught red-handed by this mighty AA Sir while gossiping with his friends during class time. AA Sir gave him a painful punishment.
As a part of the punishment, Hasinur received a book named Art of prefix . The book has n words in it. AA Sir will give Hasinur a word S and Hasinur will have to find the word that has S as a prefix in it and appears a maximum time in that particular book.
I know. That sounds brutal, right? But AA Sir isn’t even happy with this amount of punishment. He added, in case of multiple words Hasinur will have to find the lexicographic-ally smallest word. Also, he will have to tell how many times this word has appeared in that book.
Yes, Hasinur indeed is in big trouble. He will have to reply q times to his teacher else he won’t be able to go home and the chance of getting more punishment is bright. Now, he wants your help to solve this problem. Can you help him?
The first line consists of an integer n, the number of words in the textbook. The next n lines consist of the words in the book. The next line consists of an integer, the number of queries. Next q lines consists of a string S.
Constraints:
For 30 points:
1 <= n <= 10^3
1 <= q <= 10^3
1 <= word length <= 10
For 100 points:
1 <= n <= 5*10^5
1 <= q <= 10^5
1 <= word length <= 10
All the characters in the word are small letters of the English alphabet.
For each query print 'Case X: Y Z'.
Where:
X = Query Number .
Y = String corresponding to answer.
Z = The number of appearing Y string in the book.
Else print 'Case X: -1'. In case, there is no answer.
| 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 |