The Punishment of Hasinur

Shahwat_Has9 SCB-PA Inter School and C...
Limits 1s, 1.5 GB

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?

Input

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.

Output

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.

Sample

InputOutput
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

Submit

Login to submit.

Statistics

48% Solution Ratio
NirjhorEarliest, Oct '19
setulovelegendFastest, 0.2s
prodip_bsmrstuLightest, 62 MB
JisangainShortest, 1233B
Toph uses cookies. By continuing you agree to our Cookie Policy.