C. Сколько строк меньше
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан набор $$$D$$$ из $$$n$$$ строк и строка $$$s$$$. Требуется быстро находить число строк, лексикографически меньших $$$s$$$, в наборе $$$D$$$.

С заданной строкой $$$s$$$ выполняются $$$q$$$ модификаций, каждая из которых задается парой из числа $$$k_i$$$ и символа $$$c_i$$$. Модификация $$$(k_i, c_i)$$$ заключается в том, что все символы строки $$$s$$$, начиная с $$$k_i$$$ и до конца строки, заменяются на символ $$$c_i$$$.

Например, пусть исходно строка $$$s$$$ была равна «anatoly», тогда последовательность запросов $$$(5, \mathtt{o})$$$, $$$(3, \mathtt{b})$$$, $$$(7, \mathtt{x})$$$ будет менять строку следующим образом:

«anatoly» $$$\to$$$ «anatooo» $$$\to$$$ «anbbbbb» $$$\to$$$ «anbbbbx»
После каждого изменения строки $$$s$$$ требуется вывести количество строк в наборе $$$D$$$, которые лексикографически меньше, чем $$$s$$$.
Примечание

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если $$$a \ne b$$$ и выполнено одно из двух условий:

  • $$$a$$$ является префиксом строки $$$b$$$;
  • для некоторого $$$i$$$ первые $$$i$$$ символов строки $$$a$$$ равны соответствующим символам строки $$$b$$$, а $$$a_{i+1} \lt b_{i+1}$$$.
Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$q$$$ — количество строк в наборе $$$D$$$ и количество модификаций ($$$1 \le n, q \le 10^6$$$).

Во второй строке находится строка $$$s$$$, состоящая из не более чем $$$10^6$$$ строчных латинских букв.

В следующих $$$n$$$ строках содержатся строки набора $$$D$$$. Каждая строка состоит из строчных латинских букв. Суммарная длина строк в $$$D$$$ не превосходит $$$10^6$$$.

Следующие $$$q$$$ строк содержат описания модификаций. Описание состоит из числа $$$k_i$$$ и строчной буквы латинского алфавита $$$c_i$$$, разделенных пробелом ($$$1 \le k_i \le |s|$$$).

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

В первой строке выведите число строк в наборе $$$D$$$, которые лексикографически меньше изначальной строки $$$s$$$.

Затем выведите $$$q$$$ строк. В $$$i$$$-й строке выведите ответ после $$$i$$$-й модификации.

Примеры
Входные данные
4 3
anatoly
boris
anatooo
anbbbbu
anba
5 o
3 b
7 x
Выходные данные
0
0
2
3
Входные данные
5 5
abcde
buz
ababa
build
a
aba
1 b
3 z
2 u
4 z
1 a
Выходные данные
3
3
3
4
4
1
Примечание

В первом тесте из примера строка изменяется следующим образом:

«anatoly» $$$\to$$$ «anatooo» $$$\to$$$ «anbbbbb» $$$\to$$$ «anbbbbx».
  • Изначальная строка «anatoly» лексикографически меньше всех строк набора, поэтому ответ на задачу $$$0$$$.
  • После первого изменения строка становится «anatooo» и такая строка есть в наборе, однако ответ на задачу по прежнему будет $$$0$$$, так как она не меньше, текущей.
  • Затем строка становится «anbbbbb», что лексикографически больше, чем «anatooo» и «anba», но меньше чем «anbbbbu» и «boris», таким образом ответ $$$2$$$.
  • После последнего изменения строка станет «anbbbbx», что лексикографически больше «anatooo», «anba» и «anbbbbu», ответ $$$3$$$.