Опечатки

면접 대비

시간 제한2초메모리 제한64 MB

요약

각 질의 단어마다 양쪽에서 최대 한 글자씩 지워 같게 만들 수 있는 사전 단어의 개수를 세고, 일치하는 단어가 정확히 하나면 그 단어도 출력한다.

난이도: 보통10점 중 6점
유형: 문자열, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

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

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

출력

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

예제1

예제 1

입력

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