오타 자동 수정

오타를 자동으로 고쳐 주는 맞춤법 검사기를 만들려고 한다.

이 검사기가 고칠 수 있는 오타는 다음 세 가지뿐이다.

1. 글자 하나를 덜 쓰거나(예: letter를 leter로) 더 쓴 경우(예: letter를 lettter로).
2. 글자 하나를 잘못 쓴 경우(예: letter를 ketter로).
3. 이웃한 두 글자의 순서가 바뀐 경우(예: letter를 lettre로).

검사기 안에는 단어 사전이 들어 있고, 이 사전으로 오타를 고친다. 사용자가 입력한 단어가 사전에 있으면 올바른 단어이다. 사전에 없으면 사전에 있는 단어 가운데 가장 비슷한 단어로 바꾼다.

단어 $A$에 위의 세 가지 방법 가운데 하나를 딱 한 번 적용해 사전에 있는 단어 $B$를 만들 수 있으면, 두 단어 $A$와 $B$는 비슷하다고 한다. 비슷한 단어가 사전에 하나도 없으면 알 수 없는 단어로 보고 고치지 않는다.

첫째 줄에 사전에 있는 단어의 개수 $n$이 주어진다. ($n \le 10000$)

다음 $n$개 줄에 사전 단어가 한 줄에 하나씩 주어진다.

그다음 줄에 검사할 단어의 개수 $q$가 주어진다. ($q \le 1000$)

다음 $q$개 줄에 검사할 단어가 한 줄에 하나씩 주어진다.

모든 단어는 알파벳 소문자로만 이루어지며 길이는 $1$자 이상 $25$자 이하이다.

검사할 각 단어마다 한 줄씩, 입력으로 주어진 단어에 이어 다음 세 가지 중 하나를 출력한다.

• w is correct: 그 단어가 사전에 있는 경우.
• w is a misspelling of x: 그 단어가 사전에 없고, x가 사전에서 그 단어와 비슷한 단어인 경우. 비슷한 단어가 여러 개이면 입력에서 먼저 나온 단어를 출력한다.
• w is unknown: 위의 두 경우가 아닌 경우.

여기서 w는 입력으로 주어진 검사 단어이다.