Automatic Typo Correction

Interview

Time limit1sMemory limit128 MB

Summary

Given a dictionary, classify each queried word as correct, a misspelling of the first similar dictionary word, or unknown, using three specific edit types.

Level: Medium5 of 10
Topics: String, Hash map, Implementation, Brute force
Solved: No attempts yet

Problem

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

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

One letter is missing (e.g. letter typed as leter) or one extra letter is added (e.g. letter typed as lettter).
One letter is wrong (e.g. letter typed as ketter).
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.

Input

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$ .

Output

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.

Examples6

Example 1

Input

10
this
is
a
dictionary
that
we
will
use
for
us
6
su
as
the
dictonary
us
willl

Expected output

su is a misspelling of us
as is a misspelling of is
the is unknown
dictonary is a misspelling of dictionary
us is correct
willl is a misspelling of will

Example 2

Input

3
apple
banana
cherry
3
apple
banana
cherry

Expected output

apple is correct
banana is correct
cherry is correct

Example 3

Input

2
abc
xyz
2
mmm
pqr

Expected output

mmm is unknown
pqr is unknown

Example 4

Input

1
abcd
1
abdc

Expected output

abdc is a misspelling of abcd

Example 5

Input

1
hello
1
helo

Expected output

helo is a misspelling of hello

Example 6
Input
```
1
hi
1
hii
```
Expected output
```
hii is a misspelling of hi
```