Automatic Typo Correction

We want to build a spell-checker that fixes typos automatically.

The checker can fix only the following three kinds of typos:

1. One letter is missing (e.g. letter typed as leter) or one extra letter is added (e.g. letter typed as lettter).
2. One letter is wrong (e.g. letter typed as ketter).
3. Two adjacent letters are swapped (e.g. letter typed as lettre).

The checker holds a dictionary of words and uses it to correct typos. If the word the user typed is in the dictionary, it is correct. Otherwise it is replaced with the most similar word in the dictionary.

Two words $A$ and $B$ are called similar if word $A$ can be turned into dictionary word $B$ by applying exactly one of the three methods above exactly once. If no similar word exists in the dictionary, the word is treated as unknown and is not corrected.

The first line contains the number of words in the dictionary, $n$ ($n \le 10000$).

Each of the next $n$ lines contains one dictionary word.

The next line contains the number of words to check, $q$ ($q \le 1000$).

Each of the next $q$ lines contains one word to check.

Every word consists of lowercase letters only and has length between $1$ and $25$.

For each word to check, print one line: the given word followed by one of the following.

• w is correct: the word is in the dictionary.
• w is a misspelling of x: the word is not in the dictionary and x is a dictionary word similar to it. If several similar words exist, print the one that appears earliest in the input.
• w is unknown: neither of the above holds.

Here w is the word to check that was given in the input.