Вам предлагается написать программу для проверки правописания.

Задан произвольный текст. Слова в этом тексте состоят из больших и маленьких латинских букв, все остальные символы считаются разделителями. При наборе текста в словах иногда возникают ошибки, которые делятся на 4 вида:

·        замена одной буквы другой (например, cst вместо cat)

·        дублирование буквы (например, caat вместо cat)

·        пропуск буквы (например, ct вместо cat)

·        перестановка двух рядом стоящих букв (например, cta вместо cat)

Примем следующее допущение – будем считать, что при наборе текста в каждом слове может быть допущено не более одной ошибки, которая может быть любой из вышеперечисленных четырёх.

Кроме текста, задан словарь - набор правильно написанных слов.

Ваша программа должна найти слова в исходном тексте, которые отсутствуют в словаре, и предложить варианты правильного написания при их наличии. Регистр символов не учитывается (например, слово cat может быть получено из слова CST одной заменой символа S на a. Однако, обратите внимание, что регистр учитывается при выводе результатов – см. формат выходных данных).

 

В первой строке входного файла находится целое число K – количество слов в словаре . В следующих K строках располагаются слова словаря в лексикографическом порядке, каждое слово в отдельной строке, длины слов не превышают 20 символов, используются только символы нижнего регистра.

В следующей строке находится целое число N – количество строк текста . В следующих N строках располагается  текст, каждая строка не превышает 80 символов, все слова в тексте не превышают 20 символов.

В выходной файл для каждого слова в исходном тексте, которое отсутствует в словаре, выведите в отдельной строке через пробел:

·        слово из исходного текста,

·        номер строки в исходном тексте и номер слова в этой строке

·        перечень слов из словаря (в любом порядке), из которых могло бы быть получено данное слово вследствие одной ошибки. Если таких слов нет, выведите “NO VARIANTS”. Если таких слов больше трех, выведите любые три из них, затем многоточие "...".

Слова из исходного текста должны быть выведены в том же регистре, как в исходном тексте. Слова из словаря выводятся в нижнем регистре, как они записаны в словаре.

Строки должны быть выведены в порядке, в котором слова встречаются в исходном тексте.

Пример

STDIN	STDOUT
12 amount as growing if in information it number of rapidly the this 2 Thi amaunt of infomatin is growin rapidly.	Thi 1 1 this the amaunt 1 2 amount infomatin 1 4 NO VARIANTS is 2 1 as in it... growin 2 2 growing