Перед тем как стать успешным трейдером, Василий закончил университет. Во время его обучения произошел один случай, после которого Василий стал намного внимательнее слушать условия заданий для домашней работы. Далее приведено формальное условие домашнего задания в том виде, как его услышал Василий.
Дана строка $$$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 12 aaabccccc 4 a 4 b 2 b 5 a 1 b 6 b 5 c 2 a 1 a 5 a 6 b 7 b
0 1 2 2 1 2 1 2 2 2 2 2
Рассмотрим состояния строки после каждого запроса:
- $$$s = $$$«aaaaccccc». В этом случае строка не содержит «abc» как подпоследовательность, поэтому замен делать не требуется.
- $$$s = $$$«aaabccccc». В этом случае можно сделать 1 замену и получить, например, строку $$$s = $$$«aaaaccccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«ababccccc». В этом случае можно сделать 2 замены и получить, например, строку $$$s = $$$«aaaaccccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«ababacccc». В этом случае можно сделать 2 замены и получить, например, строку $$$s = $$$«aaaaacccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«bbabacccc». В этом случае можно сделать 1 замену и получить, например, строку $$$s = $$$«bbacacccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«bbababccc». В этом случае можно сделать 2 замены и получить, например, строку $$$s = $$$«bbacacccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«bbabcbccc». В этом случае можно сделать 1 замену и получить, например, строку $$$s = $$$«bbcbcbccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«baabcbccc». В этом случае можно сделать 2 замены и получить, например, строку $$$s = $$$«bbbbcbccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«aaabcbccc». В этом случае можно сделать 2 замены и получить, например, строку $$$s = $$$«aaacccccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«aaababccc». В этом случае можно сделать 2 замены и получить, например, строку $$$s = $$$«aaacacccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«aaababccc». В этом случае можно сделать 2 замены и получить, например, строку $$$s = $$$«aaacacccc». Эта строка не содержит «abc» как подпоследовательность.
- $$$s = $$$«aaababbcc». В этом случае можно сделать 2 замены и получить, например, строку $$$s = $$$«aaababbbb». Эта строка не содержит «abc» как подпоследовательность.
