TRYCOMP - Try to complete

You are given hundreds of thousands of words from a book.

For each query you are given a string S. Find the most occurring word in the book with S as prefix.

Input

The first line consists of an integer n, the number of words in the text book. The next n lines consists of the words in the book. The next line consists of an integer q, the number of queries. Next q lines consists a string S.

Output

For each query String S, print the most occurring word in the book with S as prefix along with the number of occurrences of that word. If there are many such words, print the lexicographically smallest word. If there is no such word, print -1.

Constraints

1 <= n <= 5*10^5

1 <= q <= 10^5

1 <= word length <= 10

All the characters in the word are lowercase letters of the English alphabet.

Sample

Input
10
apple
banana
orange
applet
banana
oriental
orange
oriental
applet
bangalore
8
ban
bang
app
or
oriental
apple
hobbits
oranges

Output
banana 2
bangalore 1
applet 2
orange 2
oriental 2
applet 2
-1
-1

Problem source: Inspired from autocomplete feature on Google keyboard.


Added by:cegprakash
Date:2016-10-22
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF

hide comments
2024-07-29 15:22:20
Try this Test Case:
4
aabb
aaba
aaca
aaca
1
a
==== OUTPUT =======
aaca 2
2021-12-08 16:40:46
for input given by Waseem Ahmed
Input--------
16
apple
banana
orange
oranges
applet
bangalore
oriental
oranges
oriental
appleting
bangalore
banana
ban
ban
try
this
8
ban
b
app
orientx
or
appleting
h
orange


Output---
ban 2
ban 2
apple 1
-1
oranges 2
appleting 1
-1
oranges 2
2021-07-31 20:19:41 Waseem Ahmed
Test case for those getting a WA

16
apple
banana
orange
oranges
applet
bangalore
oriental
oranges
oriental
appleting
bangalore
banana
ban
ban
try
this


8
ban
b
app
orientx
or
appleting
h
orange
2021-02-02 23:00:04
i want hint i have alot of wrong answer .....!
any one help me plz.
mycode : <snip>

[NG]: Don't post code here, use forum for review and debug help.

Last edit: 2021-02-03 00:34:12
2020-09-07 06:08:24
Nice problem! Solved it using trie.
2020-04-27 17:06:02
AC in one go in Java
2016-12-24 13:42:24 testing java
time limit is too tight for java : (

Last edit: 2016-12-28 19:30:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.