D. Поиск строк
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$s$$$ содержащий $$$n$$$ различных строк. Каждая строка состоит из $$$m$$$ строчных букв латинского алфавита.

Вам необходимо ответить на $$$q$$$ запросов. Каждый запрос содержит строку $$$t$$$ длины $$$m+1$$$. Посчитайте количество индексов $$$i$$$, таких что, строку $$$t$$$ можно получить из строки $$$s_i$$$, если разрешено вставить одну букву в произвольную позицию.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le m \le 10$$$) — размер массива и длина строк.

Следующие $$$n$$$ строк содержат строки $$$s_i$$$. Все заданные строки различны.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.

Следующие $$$q$$$ строк содержат строки запросов $$$t$$$ длины $$$m + 1$$$.

Выходные данные

Для каждого запроса выведите количество индексов $$$i$$$, таких что, строку из запроса можно получить из строки $$$s_i$$$, если разрешено вставить одну букву в произвольную позицию.

Примеры
Входные данные
2 1
a
c
4
aa
ca
mm
cf
Выходные данные
1
2
0
1
Входные данные
6 3
dba
abd
cbb
ada
add
bdd
5
ccbb
abdd
adba
bada
dddd
Выходные данные
1
3
2
1
0
Примечание

Объяснение первого теста из условия:

  • строка a может быть превращена в aa вставкой одной буквы;
  • и строка a, и строка c может быть превращена в строку ca вставкой одной буквы;
  • ни a, ни c не может быть превращена в mm вставкой одной буквы;
  • c можно превратить в cf вставкой одной буквы.