E. Некрасивые строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем букву разрешенной, если она — строчная и является одной из первых $$$k$$$ букв латинского алфавита.

Вам задана строка $$$s$$$ длины $$$n$$$, состоящая только из разрешенных букв.

Назовем некоторую строку $$$t$$$ красивой, если $$$t$$$ является подпоследовательностью $$$s$$$.

Вам заданы $$$q$$$ строк $$$t_1, t_2, \dots, t_q$$$. Все они состоят только из разрешенных букв. Для каждой строки $$$t_i$$$ определите, какое наименьшее количество разрешенных букв вам нужно приписать к ней справа, чтобы она перестала быть красивой.

Последовательность $$$t$$$ является подпоследовательностью $$$s$$$, если $$$t$$$ может быть получена из $$$s$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^6$$$; $$$1 \le k \le 26$$$) — длина строки $$$s$$$ и количество разрешенных букв.

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

В третьей строке задано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

В следующих $$$q$$$ строках заданы сами запросы: в $$$i$$$-й строке задана строка $$$t_i$$$, состоящая только из разрешенных букв.

Дополнительное ограничение на входные данные: суммарная длина всех $$$t_i$$$ не превосходит $$$10^6$$$.

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

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

Примеры
Входные данные
7 3
abacaba
3
cc
bcb
b
Выходные данные
0
1
2
Входные данные
5 1
aaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa
Выходные данные
5
4
3
2
1
0
Примечание

В первом примере:

  1. Строка cc уже является некрасивой, поэтому приписывать к ней ничего не нужно;
  2. bcb — красивая, поэтому к ней нужно приписать хотя бы одну букву справа: bcba не подойдет, а вот bcbb и bcbc — уже некрасивые.
  3. К b нужно приписать хотя бы две буквы, так как ba, bb и bc — красивые. Например, можно получить строку bbb.