Перед тем как стать успешным трейдером, Василий закончил университет. Во время его обучения произошел один случай, после которого Василий стал намного внимательнее слушать условия заданий для домашней работы. Далее приведено правильное формальное условие домашнего задания.
Дана строка $$$s$$$ длины $$$n$$$, состоящая только из символов «a», «b» и «c». Есть $$$q$$$ запросов вида ($$$pos, c$$$), который обозначает замену элемента строки $$$s$$$ на позиции $$$pos$$$ на символ $$$c$$$. После каждого запроса требуется вывести минимальное количество символов в строке, которые нужно заменить, чтобы строка не содержала строку «abc» в качестве подстроки. Правильной заменой символа является его изменение на символ «a», «b» или «c».
Строка $$$x$$$ является подстрокой $$$y$$$, если $$$x$$$ может быть получена из $$$y$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Первая строка ввода содержит два целых числа $$$n$$$ и $$$q$$$ $$$(1 \le n, q \le 10^5)$$$ — длину строки и количество запросов соответственно.
Следующая строка ввода содержит строку $$$s$$$, состоящую из символов «a», «b» и «c».
Следующие $$$q$$$ строк содержат целое число $$$i$$$ и символ $$$c$$$ $$$(1 \le i \le n)$$$ — индекс и значение нового элемента строки соответственно. Гарантируется, что символ $$$c$$$ равен значению «a», «b» или «c».
Для каждого запроса выведите минимальное количество символов, которые необходимо заменить, чтобы строка не содержала «abc» как подстроку.
9 10 abcabcabc 1 a 1 b 2 c 3 a 4 b 5 c 8 a 9 b 1 c 4 a
3 2 2 2 1 2 1 1 1 0
Рассмотрим состояния строки после каждого запроса:
- $$$s =$$$ «abcabcabc». В этом случае можно сделать $$$3$$$ замены и получить, например, строку $$$s =$$$ «bbcaccabb». Эта строка не содержит «abc» как подотрезок.
- $$$s =$$$ «bbcabcabc». В этом случае можно сделать $$$2$$$ замены и получить, например, строку $$$s =$$$ «bbcbbcbbc». Эта строка не содержит «abc» как подотрезок.
- $$$s =$$$ «bccabcabc». В этом случае можно сделать $$$2$$$ замены и получить, например, строку $$$s =$$$ «bccbbcbbc». Эта строка не содержит «abc» как подотрезок.
- $$$s =$$$ «bcaabcabc». В этом случае можно сделать $$$2$$$ замены и получить, например, строку $$$s =$$$ «bcabbcbbc». Эта строка не содержит «abc» как подотрезок.
- $$$s =$$$ «bcabbcabc». В этом случае можно сделать $$$1$$$ замену и получить, например, строку $$$s =$$$ «bcabbcabb». Эта строка не содержит «abc» как подотрезок.
- $$$s =$$$ «bcabccabc». В этом случае можно сделать $$$2$$$ замены и получить, например, строку $$$s =$$$ «bcabbcabb». Эта строка не содержит «abc» как подотрезок.
- $$$s =$$$ «bcabccaac». В этом случае можно сделать $$$1$$$ замену и получить, например, строку $$$s =$$$ «bcabbcaac». Эта строка не содержит «abc» как подотрезок.
- $$$s =$$$ «bcabccaab». В этом случае можно сделать $$$1$$$ замену и получить, например, строку $$$s =$$$ «bcabbcaab». Эта строка не содержит «abc» как подотрезок.
- $$$s =$$$ «ccabccaab». В этом случае можно сделать $$$1$$$ замену и получить, например, строку $$$s =$$$ «ccabbcaab». Эта строка не содержит «abc» как подотрезок.
- $$$s =$$$ «ccaaccaab». В этом случае строка не содержит «abc» как подотрезок, поэтому замен делать не требуется.
