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