\(n\) игроков собираются провести турнир по игре «камень-ножницы-бумага». Как вы наверное знаете, при игре один на один в камень-ножницы-бумагу каждый из игроков выбирает себе предмет независимо друг от друга. Затем результат определяется в зависимости от выбранных предметов: "бумага" побеждает "камень", "камень" побеждает "ножницы", "ножницы" побеждают "бумагу", и два одинаковых предмета приводят к ничьей.
В начале турнира все игроки будут стоять в ряд. Они пронумерованы по возрастанию от \(1\) до \(n\) от самого левого игрока к самому правому. Каждый игрок имеет заранее выбранный предмет, который он будет использовать в каждой игре на протяжении всего турнира. Вот как будет проводиться турнир:
- Если остался только один игрок, он объявляется победителем.
- Иначе, в ряду выбираются произвольно два соседних игрока. Они играют следующий матч. Проигравший игрок выбывает из турнира и покидает свое место в ряду (его бывшие соседи становятся соседями). Если игра завершилась ничьей, проигравший игрок определяется подбрасыванием монеты.
Организаторы знают о предпочтительных предметов всех игроков. Они хотят узнать общее количество игроков, у которых есть шанс стать победителем турнира (это значит, что есть подходящий способ выбрать порядок игр и манипулировать бросками монет). Тем не менее, некоторые игроки все еще оптимизируют свою стратегию и могут сообщить организаторам о своих новых предпочтительных предметах. Можете ли вы найти количество возможных победителей после каждого такого запроса?
Выходные данные
Выведите \(q + 1\) целое число \(r_0, \ldots, r_q\), где \(r_k\) это количество игроков, которые могут стать победителями после применения первых \(k\) изменений.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
RPS
1 S
2 R
3 P
1 P
2 P
|
2
2
1
2
2
3
|