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.