A password's neighbours

A service checks new passwords: is a password within a few edits of a common one? An edit is an insertion, deletion or substitution of one character. The dictionary is common passwords in decreasing order of frequency, the first being the most common. For each query find how many passwords of the dictionary lie at most k edits from it, and the most common of them.

Tests three to six are the 10,000 most common passwords from the open SecLists list, and the queries are common passwords with typos and random strings.

Input

The first line holds n (1 ≤ n ≤ 10⁴), then n different passwords, one per line. Then the number of queries q (1 ≤ q ≤ 300) and q lines: a password and k (0 ≤ k ≤ 2), with at most twenty queries having k = 2. Passwords are 1 to 20 printable ASCII characters without spaces.

Output

For each query, the number of passwords of the dictionary at most k edits away and the most common of them, separated by a space. If there are none, 0 -.

Examples

Example 1

Input

6
password
123456
qwerty
passw0rd
qwerty1
dragon
5
qwerty 0
qwerty 1
pasword 1
pasword 2
monkey 2

Output

1 qwerty
2 qwerty
1 password
2 password
0 -

Example 2

Input

5
abc
abd
xbc
abcd
zzz
4
abc 1
ab 1
zz 0
bcd 2

Output

4 abc
2 abc
0 -
4 abc

Limits

Time · Python: 18500 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Comparing the query with each password is 3 · 10⁶ edit distance tables per test. Can comparing the query with one password x tell you at once that many others are far away?

2Hint 2

If d(q, x) = 9 and d(x, w) = 4, then by the triangle inequality d(q, w) ≥ 5. Arrange the passwords in advance by their distance to one of them, and so on recursively.

3The idea

A BK-tree. A node is a password, and the edge to a child is labelled with the distance between them. For a query within k: at a node at distance d, go down only the edges e in [d − k, d + k]; in the other subtrees all passwords are farther than k.

4Walkthrough

Insert the passwords in order of frequency: the first is the root, and each next one goes down by the edge of its distance until it finds a free place. A node's number equals the password's number, so the most common of those found is the one with the smallest number. The walk uses its own stack: the depth of the tree of 10,000 passwords is 26.

For one edit there is another way: generate all strings one edit from the query, about (2L + 1) · 95 of them, and look each up in a hash table. For two edits there are already hundreds of thousands of variants, while the tree visits a fifth of the dictionary; that is why there are few such queries in the tests.

4+Solution

5Complexity

Building costs about the depth in comparisons per password. A query with one edit on this dictionary compares a few percent of the passwords on average, with two about a fifth; the BK-tree has no worst-case bound better than brute force.

6Common mistakes

Comparing with all. This is wrong.py: 300 queries on 10,000 passwords are three million tables, and in the third test the time runs out.
The window on one side. If only edges above d + k are discarded, the answer stays right, but the tree visits a lot more than needed: edges below d − k are not needed either.
The most common is not the first found. The walk does not go in order of numbers; the minimum number has to be tracked separately.
Recursion on a tree of depth 26 works, but with an unlucky insertion order, alphabetical for example, the tree can be much deeper.

Algorithms behind it

STR Data structure BK-tree All passwords one or two edits from a given one: the triangle inequality cuts off whole branches, and where it stops helping. O(N · depth) to build 1 problem STR Algorithm Edit distance The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it. O(m · n) 2 problems