Teemu has used text editor Sentence and especially its spell checker. Unfortunately, the last update broke the spell checker and Teemu is quite a bad writer. To add insult to injury, Teemu needs to return a literature analysis tomorrow without any spelling mistakes or he will fail the course.

The spell checker works by having a dictionary $d$ of valid words. When a word $w_i$ s written, the program compares it to all words in the dictionary $d$ to determine the closest match. The closest match is the word in $d$ whose edit distance to $w_i$ is smallest. In case of ties with edit distance, the word which is lexicographically smallest is chosen as the closest match.

Help Teemu by writing him a spell checker.

For a description of edit distance, see this homework task.

Input

The first line of input consists of single integer $n$, the number of words in dictionary $d$. Next $n$ lines contain all words in $d$ in lexicographical order.

After the dictionary follows a line with single integer $q$, the number of words to spell check. Next $q$ lines contain words $w_i$ to spell check.

Each word in the dictionary and being checked consists of characters a-z.

Output

Output single line for each word being spell checked. The line shall contain integer $e_i$ and word $r_i$, the edit distance between $w_i$ and the closest match, and the closest match $e_i$.

Limits

• $1 \le n \le 4\cdot10^5$
• $1 \le \text{length}(s_i) \le 32$
• $1 \le \sum_{i=0}^n\text{length}(s_i) \le 5\cdot10^6$
• $1 \le q \le 10$

Example

Input:

6
car
cat
feather
weather
wether
whether
5
car
bat
cas
teather
weater

Output:

0 car
1 cat
1 car
1 feather
1 weather