시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 7 4 80.000%

문제

상근이는 오타를 자동으로 수정해주는 프로그램을 만드려고 한다.

상근이의 프로그램이 고칠 수 있는 오타는 다음과 같은 세 가지 종류이다.

1. 한 글자를 적게 썼을 때 (letter를 leter로 쓴 경우), 한 글자를 많이 썼을 때 (letter를 lettter로 쓴 경우)

2. 한 글자를 잘못 적었을 때 (letter를 ketter로 쓴 경우)

3. 인접한 두 글자의 순서가 잘못 되었을 때 (letter를 lettre로 쓴 경우)

오타 수정 프로그램의 내부에는 단어 사전이 있고, 이 사전을 이용해서 오타를 수정한다. 만약, 사용자가 입력한 단어가 사전에 없는 경우에는, 사전에 있는 단어 중 가장 비슷한 단어로 변경한다. 단어 A를 위의 세 가지 방법 중 하나를 한 번 이용해서 사전에 있는 단어 B로 바꿀 수 있을 때, 두 단어 A와 B를 비슷하다고 한다. 비슷한 단어가 사전에 없는 경우에는 알 수 없는 단어로, 오타 수정을 하지 않는다.

입력

첫째 줄에는 단어 사전에 있는 단어의 수 n이 주어진다. (n ≤ 10000) 다음 n개 줄에는 단어 사전에 있는 단어가 한 줄에 하나씩 주어진다. 다음 줄에는 오타 수정 프로그램을 이용해 수정할 단어의 수 q가 주어진다. (q ≤ 1000) 다음 q개 줄에는 수정할 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자 1개~25개로 이루어져 있다.

출력

각각의 수정할 단어에 대해서, 입력으로 주어진 단어와 아래 세 가지 중 하나를 출력한다.

1. is correct: 단어 사전에 있는 단어인 경우
2. is a misspelling of <x>: 입력으로 주어진 단어가 단어 사전에 없고, <x>가 그 단어와 가장 비슷한 단어일 때. 가능한 <x>가 여러가지 인 경우에는 입력으로 주어지는 순서가 앞선 것을 출력한다.
3. is unknown: 위의 두 경우가 아닐 때

예제 입력 1

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

예제 출력 1

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

힌트

W3sicHJvYmxlbV9pZCI6IjY1MTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjRcdWQwYzAgXHVjNzkwXHViM2Q5IFx1YzIxOFx1YzgxNSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzYyNFx1ZDBjMFx1Yjk3YyBcdWM3OTBcdWIzZDlcdWM3M2NcdWI4NWMgXHVjMjE4XHVjODE1XHVkNTc0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YWNlMFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYyNFx1ZDBjMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzEzOCBcdWFjMDBcdWM5YzAgXHVjODg1XHViOTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4xLiBcdWQ1NWMgXHVhZTAwXHVjNzkwXHViOTdjIFx1YzgwMVx1YWM4YyBcdWMzN2NcdWM3NDQgXHViNTRjIChsZXR0ZXJcdWI5N2MgbGV0ZXJcdWI4NWMgXHVjNGY0IFx1YWNiZFx1YzZiMCksIFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWI5N2MgXHViOWNlXHVjNzc0IFx1YzM3Y1x1Yzc0NCBcdWI1NGMgKGxldHRlclx1Yjk3YyBsZXR0dGVyXHViODVjIFx1YzRmNCBcdWFjYmRcdWM2YjApPFwvcD5cclxuXHJcbjxwPjIuIFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjNzk4XHViYWJiIFx1YzgwMVx1YzVjOFx1Yzc0NCBcdWI1NGMgKGxldHRlclx1Yjk3YyBrZXR0ZXJcdWI4NWMgXHVjNGY0IFx1YWNiZFx1YzZiMCk8XC9wPlxyXG5cclxuPHA+My4gXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWFlMDBcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHVhYzAwIFx1Yzc5OFx1YmFiYiBcdWI0MThcdWM1YzhcdWM3NDQgXHViNTRjIChsZXR0ZXJcdWI5N2MgbGV0dHJlXHViODVjIFx1YzRmNCBcdWFjYmRcdWM2YjApPFwvcD5cclxuXHJcbjxwPlx1YzYyNFx1ZDBjMCBcdWMyMThcdWM4MTUgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzU4IFx1YjBiNFx1YmQ4MFx1YzVkMFx1YjI5NCBcdWIyZThcdWM1YjQgXHVjMGFjXHVjODA0XHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNzc0IFx1YzBhY1x1YzgwNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNjI0XHVkMGMwXHViOTdjIFx1YzIxOFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YjJlOFx1YzViNFx1YWMwMCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWJlNDRcdWMyYjdcdWQ1NWMgXHViMmU4XHVjNWI0XHViODVjIFx1YmNjMFx1YWNiZFx1ZDU1Y1x1YjJlNC4gXHViMmU4XHVjNWI0IEFcdWI5N2MgXHVjNzA0XHVjNzU4IFx1YzEzOCBcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVkNTVjIFx1YmM4OCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjQgQlx1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWIyZThcdWM1YjQgQVx1YzY0MCBCXHViOTdjIFx1YmU0NFx1YzJiN1x1ZDU1OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmU0NFx1YzJiN1x1ZDU1YyBcdWIyZThcdWM1YjRcdWFjMDAgXHVjMGFjXHVjODA0XHVjNWQwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTRjIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHViMmU4XHVjNWI0XHViODVjLCBcdWM2MjRcdWQwYzAgXHVjMjE4XHVjODE1XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlOFx1YzViNCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChuICZsZTsgMTAwMDApIFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZThcdWM1YjQgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzYyNFx1ZDBjMCBcdWMyMThcdWM4MTUgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWMyMThcdWM4MTVcdWQ1NjAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxOCBxXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKHEgJmxlOyAxMDAwKSBcdWIyZTRcdWM3NGMgcVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjODE1XHVkNTYwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwIDFcdWFjMWN+MjVcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHVjODE1XHVkNTYwIFx1YjJlOFx1YzViNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0XHVjNjQwIFx1YzU0NFx1Yjc5OCBcdWMxMzggXHVhYzAwXHVjOWMwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4xLiBpcyBjb3JyZWN0OiBcdWIyZThcdWM1YjQgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NzggXHVhY2JkXHVjNmIwPGJyIFwvPlxyXG4yLiBpcyBhIG1pc3NwZWxsaW5nIG9mICZsdDt4Jmd0OzogXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIyZThcdWM1YjRcdWFjMDAgXHViMmU4XHVjNWI0IFx1YzBhY1x1YzgwNFx1YzVkMCBcdWM1YzZcdWFjZTAsICZsdDt4Jmd0O1x1YWMwMCBcdWFkZjggXHViMmU4XHVjNWI0XHVjNjQwIFx1YWMwMFx1YzdhNSBcdWJlNDRcdWMyYjdcdWQ1NWMgXHViMmU4XHVjNWI0XHVjNzdjIFx1YjU0Yy4gXHVhYzAwXHViMmE1XHVkNTVjICZsdDt4Jmd0O1x1YWMwMCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzAgXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM1NWVcdWMxMjAgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48YnIgXC8+XHJcbjMuIGlzIHVua25vd246IFx1YzcwNFx1Yzc1OCBcdWI0NTAgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzU0NFx1YjJkMCBcdWI1NGM8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NTE4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQXV0b21hdGljIENvcnJlY3Rpb24gb2YgTWlzc3BlbGxpbmdzIiwiZGVzY3JpcHRpb24iOiI8cD5Tb21lIHRleHQgZWRpdG9ycyBvZmZlciBhIGZlYXR1cmUgdG8gY29ycmVjdCB3b3JkcyB3aGljaCBzZWVtIHRvIGJlIHdyaXR0ZW4gaW5jb3JyZWN0bHkuIEluIHRoaXMgcHJvYmxlbSB5b3UgYXJlIGFza2VkIHRvIGltcGxlbWVudCBhIHNpbXBsZSBBdXRvbWF0aWMgQ29ycmVjdGlvbiBvZiBNaXNzcGVsbGluZ3MgKEFDTSkuPFwvcD5cclxuXHJcbjxwPkFDTSB0YWtlcyBjYXJlIG9mIHRoZSBmb2xsb3dpbmcgbWlzc3BlbGxpbmdzIG9mIHdvcmRzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPk9uZSBsZXR0ZXIgaXMgbWlzc2luZyAoZS5nLiwgbGV0dGVyIGlzIHdyaXR0ZW4gbGV0ZXIpIG9yIHRvbyBtdWNoIChlLmcuLCBsZXR0ZXIgaXMgd3JpdHRlbiBsZXR0dGVyKS48XC9saT5cclxuXHQ8bGk+T25lIGxldHRlciBpcyB3cm9uZyAoZS5nLiwgbGV0dGVyIGlzIHdyaXR0ZW4ga2V0dGVyKTxcL2xpPlxyXG5cdDxsaT5UaGUgb3JkZXIgb2YgdHdvIGFkamFjZW50IGxldHRlcnMgaXMgd3JvbmcgKGUuZy4sIGxldHRlciBpcyB3cml0dGVuIGxldHRyZSk8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5BQ00gaXMgYmFzZWQgb24gYSBkaWN0aW9uYXJ5IG9mIGtub3duIHdvcmRzLiBXaGVuIGEgdGV4dCBjb250YWlucyBhIHdvcmQgd2hpY2ggaXMgbm90IGluIHRoZSBkaWN0aW9uYXJ5LCBBQ00gd2lsbCB0cnkgdG8gcmVwbGFjZSBpdCBieSBhIHNpbWlsYXIgd29yZCBvZiB0aGUgZGljdGlvbmFyeS4gVHdvIHdvcmRzIGFyZSBzaW1pbGFyIGlmIHdlIGNhbiB0cmFuc2Zvcm0gb25lIHdvcmQgaW50byB0aGUgb3RoZXIgYnkgZG9pbmcgZXhhY3RseSBvbmUgb2YgdGhlIG1pc3NwZWxsaW5ncyBsaXN0ZWQgYWJvdmUuIEFuIHVua25vd24gd29yZCBpcyBsZWZ0IHVuY2hhbmdlZCBpZiB0aGVyZSBpcyBubyBzaW1pbGFyIHdvcmQgaW4gdGhlIGRpY3Rpb25hcnkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSB3aWxsIGdpdmUgdGhlIG51bWJlciBuIG9mIHdvcmRzIGluIHRoZSBkaWN0aW9uYXJ5IChuICZsZTsgMTAwMDApLiBUaGUgbmV4dCBuIGxpbmVzIGNvbnRhaW4gdGhlIGRpY3Rpb25hcnkgd29yZHMuIFRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIHEgJmxlOyAxMDAwLCB0aGUgbnVtYmVyIG9mIHF1ZXJ5IHdvcmRzLiBUaGUgbmV4dCBxIGxpbmVzIGNvbnRhaW4gdGhlIHF1ZXJ5IHdvcmRzLiBZb3UgbWF5IGFzc3VtZSB0aGF0IGVhY2ggd29yZCBpbiB0aGUgaW5wdXQgY29uc2lzdHMgb2YgMSB0byAyNSBsb3dlciBjYXNlIGxldHRlcnMgKCYjMzk7YSYjMzk7IHRvICYjMzk7eiYjMzk7KTxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBxdWVyeSB3b3JkLCBwcmludCBvbmUgbGluZSB3aXRoIHRoZSBxdWVyeSB3b3JkIGZvbGxvd2VkIGJ5IG9uZSBvZiB0aGUgZm9sbG93aW5nIHBvc3NpYmlsaXRpZXM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+aXMgY29ycmVjdCwgaWYgdGhlIHdvcmQgb2NjdXJzIGluIHRoZSBkaWN0aW9uYXJ5LjxcL2xpPlxyXG5cdDxsaT5pcyBhIG1pc3NwZWxsaW5nIG9mICZsdDt4Jmd0Oywgd2hlcmUgJmx0O3gmZ3Q7IGlzIGEgd29yZCBvZiB0aGUgZGljdGlvbmFyeSBzaW1pbGFyIHRvIHRoZSBxdWVyeSB3b3JkLCBhbmQgdGhlIHF1ZXJ5IHdvcmQgaXMgbm90IGluIHRoZSBkaWN0aW9uYXJ5LiBJbiB0aGUgY2FzZSB0aGF0IHRoZXJlIGFyZSBzZXZlcmFsIHBvc3NpYmlsaXRpZXMsIHNlbGVjdCB0aGUgd29yZCBmcm9tIHRoZSBkaWN0aW9uYXJ5IHdoaWNoIGFwcGVhcmVkIGVhcmxpZXIgaW4gdGhlIGlucHV0LjxcL2xpPlxyXG5cdDxsaT5pcyB1bmtub3duLCBpZiBjYXNlcyAxIGFuZCAyIGRvIG5vdCBhcHBseS48XC9saT5cclxuPFwvb2w+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==