Перед тем как стать успешным трейдером, Василий закончил университет. Во время его обучения произошел один случай, после которого Василий стал намного внимательнее слушать условия заданий для домашней работы. Далее приведено формальное условие домашнего задания в том виде, как его услышал Василий.
Дана строка \(s\) длины \(n\), состоящая только из символов «a», «b» и «c». Есть \(q\) запросов вида (\(pos, c\)), который обозначает замену элемента строки \(s\) на позиции \(pos\) на символ \(c\). После каждого запроса требуется вывести минимальное количество символов в строке, которые нужно заменить, чтобы строка не содержала строку «abc» в качестве подпоследовательности. Правильной заменой символа является его изменение на символ «a», «b» или «c».
Строка \(x\) называется подпоследовательностью строки \(y\), если \(x\) может быть получена из \(y\) с помощью удаления некоторых символов без изменения порядка оставшихся символов.
Выходные данные
Для каждого запроса выведите минимальное количество символов, которые необходимо заменить, чтобы строка не содержала «abc» как подпоследовательность.
Примечание
Рассмотрим состояния строки после каждого запроса:
- \(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» как подпоследовательность.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|