F. Победитель в Камень-Ножницы-Бумагу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$n$$$ игроков собираются провести турнир по игре «камень-ножницы-бумага». Как вы наверное знаете, при игре один на один в камень-ножницы-бумагу каждый из игроков выбирает себе предмет независимо друг от друга. Затем результат определяется в зависимости от выбранных предметов: "бумага" побеждает "камень", "камень" побеждает "ножницы", "ножницы" побеждают "бумагу", и два одинаковых предмета приводят к ничьей.

В начале турнира все игроки будут стоять в ряд. Они пронумерованы по возрастанию от $$$1$$$ до $$$n$$$ от самого левого игрока к самому правому. Каждый игрок имеет заранее выбранный предмет, который он будет использовать в каждой игре на протяжении всего турнира. Вот как будет проводиться турнир:

  • Если остался только один игрок, он объявляется победителем.
  • Иначе, в ряду выбираются произвольно два соседних игрока. Они играют следующий матч. Проигравший игрок выбывает из турнира и покидает свое место в ряду (его бывшие соседи становятся соседями). Если игра завершилась ничьей, проигравший игрок определяется подбрасыванием монеты.

Организаторы знают о предпочтительных предметов всех игроков. Они хотят узнать общее количество игроков, у которых есть шанс стать победителем турнира (это значит, что есть подходящий способ выбрать порядок игр и манипулировать бросками монет). Тем не менее, некоторые игроки все еще оптимизируют свою стратегию и могут сообщить организаторам о своих новых предпочтительных предметах. Можете ли вы найти количество возможных победителей после каждого такого запроса?

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ — количество игроков и запросов изменения предпочтительного предмета ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq q \leq 2 \cdot 10^5$$$).

Вторая строка содержит строку из $$$n$$$ символов. $$$i$$$-й из этих символов "R", "P", или "S", если игрок с номером $$$i$$$ собирается играть перед всеми изменениями, используя "камень", "бумагу", или "ножницы", соответственно.

Следующие $$$q$$$ строк описывают изменения. $$$j$$$-я из этих строк содержит целое число $$$p_j$$$ и символ $$$c_j$$$, означающий, что игрок $$$p_j$$$ будет использовать в играх предмет, обозначенный символом $$$c_j$$$, начиная с этого момента ($$$1 \leq p_j \leq n$$$).

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

Выведите $$$q + 1$$$ целое число $$$r_0, \ldots, r_q$$$, где $$$r_k$$$ это количество игроков, которые могут стать победителями после применения первых $$$k$$$ изменений.

Пример
Входные данные
3 5
RPS
1 S
2 R
3 P
1 P
2 P
Выходные данные
2
2
1
2
2
3