Задача H. Опечатки ≡

Условие

При наборе текста довольно часто возникают опечатки из-за неправильного нажатия на клавиши. Например, некоторые буквы оказываются заменены на другие, появляются лишние буквы, некоторые буквы исчезают из слов. В большинстве случаев эти опечатки можно исправить автоматически. В частности, существует метод проверки орфографии, основанный на поиске в словаре слов, похожих на проверяемые.

Два слова называются похожими, если можно удалить из каждого слова не более одной буквы так, чтобы слова стали одинаковыми, возможно пустыми. Например, слова spot и sport похожи, так как одно и то же слово spot можно получить из первого слова без удаления букв, а из второго — удалением буквы r.

Требуется написать программу, которая для каждого слова проверяемого текста определяет количество похожих на него слов в словаре.

Формат входного файла

В первой строке входного файла через пробел записаны натуральные числа% N ≥ 1 — общее количество слов в словаре и M ≥ 1 — количество слов в проверяемом тексте (N + M ≤ 20 000) В последующих N строках записаны слова, входящие в словарь, по одному на строке. Все слова словаря различны. Далее следуют M строк, в которых записаны слова проверяемого текста, по одному слову в строке.

Слова состоят из строчных и прописных букв латинского алфавита (прописные и строчные буквы считаются различными). Любое слово состоит не менее чем из одной и не более чем из 12 букв.

Формат выходного файла

Для каждого слова из текста выведите в выходной файл строку, содержащую это слово, далее через пробел количество слов из словаря, на которые оно похоже. Если в словаре имеется единственное похожее слово, то также выведите в этой строке это слово (через пробел).

Примеры тестов

5 8
father
and
or
mother
a
Father 
and 
mather 
go 
o
for 
e 
walk

Father 1 father
and 1 and
mather 2
go 1 or
o 2
for 1 or
e 1 a
walk 0