Соло на клавиатуре

Работники Министерства Быстрой Печати и Длинных Строк озабочены новой проблемой. В последнее время сложность набираемых ими текстов существенно увеличилась, и они стали допускать ошибки. К счастью, уровень подготовки в МБПДС высокий, поэтому любой работник в любом слове допускает не более одной ошибки.

Ошибки, которые могут допустить работники МБПДС, таковы:

• вместо нужной клавиши нажата соседняя;
• клавиша не нажата;
• перед нужной клавишей нажата одна из соседних клавиш;
• после нужной клавиши нажата одна из соседних клавиш;

Для клавиши на клавиатуре соседними считаются шесть клавиш: слева, справа, слева сверху, справа сверху, слева снизу, справа снизу. Клавиатура является стандартной QWERTY-клавиатурой и изображена на рисунке.

Министерство хочет автоматизировать процесс исправления ошибок. Для этого нужно написать программу, которая могла бы по данному слову, в котором допущено не более одной ошибки, выводить список словарных слов, которые могли быть введены.

Помогите работникам МБПДС и напишите такую программу.

В первой строке входного файла находится число $N$ ($1 \le N \le 5 \cdot 10^4$) --- число слов в словаре. В каждой из следующих $N$ строк содержится по одному слову из словаря. Все слова в словаре различны.

В следующей строке находится число $M$ ($1 \le M \le 5 \cdot 10^4$) --- слова, которые необходимо исправить. Каждая из следующих $M$ строк содержит по одному слову для проверки.

Все слова в файле состоят из прописных латинских букв. Во входном файле не содержится пустых строк. Размер входного файла не превышает одного мегабайта. q

Для каждого из слов, подлежащих исправлению, выведите информацию о возможных его исправлениях. Эта информация состоит из блока, включающего одну или несколько строк. Первая строка блока содержит одно целое число $C\_i$ --- число словарных слов, которые могли бы соответствовать введенному слову. Далее необходимо вывести эти словарные слова в лексикографическом порядке, по одному на каждой строке. Если $C\_i > 5$, выведите только первые пять слов.