Задача №113580. Маленький Матеж и большие проблемы

У маленького Матежа возникла проблема с решением следующей задачи.

У него есть множество слов, содержащее N слов. Ему пришло Q запросов, являющихся шаблонами. Шаблон состоит из строчных латинских букв и символа '*'.

Требуется узнать, сколько слов из множества могут совпасть с шаблоном, если вместо '*' подставить любое (возможно, пустое) множество букв.

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

В первой строке содержатся N и Q ( 1 ≤ N , Q ≤ 10 5 ). В последующих N строках содержатся строки из множества. В последующих Q строках содержатся шаблоны. Входной файл содержит не более трех миллионов символов.

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

Выведите Q строк: в каждой ответ для соответствующего шаблона.

Система оценки

40 баллов: 1 ≤ N , Q ≤ 1000

Примеры
Входные данные
3 3
aaa
abc
aba
a*a
aaa*
*aaa
Выходные данные
2
1
1
Входные данные
5 3
eedecc
ebdecb
eaba
ebcddc
eb
e*
*dca
e*c
Выходные данные
5
0
2
Сдать: для сдачи задач необходимо войти в систему