Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Punishment of Hasinur

By Shahwat_Has9 · 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

Discussion

Toph uses cookies. By continuing you agree to our Cookie Policy.