3. Подскажите, как пройти в библиотеку?

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

В открытом файле с названиями книг содержится $n, 1 \leq n \leq 10^5$ непустых строк с названиями книг, состоящих из символов латиницы, кириллицы, цифр и знаков пунктуации. Ссылка на файл с названиями книг: https://disk.yandex.ru/d/D0qv7ZV8wQAiaQ

В открытом файле с примерами запросов содержится $2 \times m$ строк, $1 \leq m \leq 10^3$. На нечетных строках идут запросы от читателей, состоящие из символов латиницы, кириллицы, цифр и знаков пунктуации. На четных строках следом за запросом всегда идёт ответ на запрос $-$ строка с названием книги $s$, гарантированно присутствующая в открытом файле с названиями книг. Ссылка на файл с открытыми примерами запросов: https://disk.yandex.ru/d/vAeVVpb1j3rzrA

На первой строке входных данных задается число $n, 1 \leq n \leq 10^5$ $-$ количество названий книг. Далее на $n$ последующих строках задаются названия книг, состоящие из символов латиницы, кириллицы, цифр и знаков пунктуации. Далее задается число $m, 1 \leq m \leq 10^4$ $-$ количество запросов к вашей программе. После чего на $m$ последующих строках задаются запросы от читателей, представляющие собой названия книг, в которых были допущены ошибки (вставка, замена или удаление произвольного количества случайных символов).

Количество названий книг, подаваемых на вход программе, их порядок и сами названия гарантированно совпадают с данными в открытом файле с названиями книг.

В качестве ответа выведите ответы на $q$ запросов. В первой строчке ответа на каждый запрос должно быть количество предлагаемых книг $1 \leq k \leq 3$, а на $k$ последующих строках $-$ названия книг. Каждое выводимое название книги обязательно должно присутствовать среди $n$ строк, содержащихся в открытом файле с названиями книг. Решение будет оцениваться на основе точности среди $k$ предлагаемых вариантов (top-k accuracy), которая должна быть не ниже $0.95$. Иначе говоря, доля запросов, среди $k$ ответов на которые есть правильный ответ, должна быть не менее $0.95$.