$$$n$$$ 玩家将参加石头剪刀布锦标赛。您可能知道,在一对一的石头剪刀布比赛中,两名玩家独立选择自己的形状。然后根据所选形状确定结果:“布”击败“石头”,“石头”击败“剪刀”,“剪刀”击败“布”,两个相同的形状会产生平局。
比赛开始时,所有玩家将站成一排,其数字从最左边玩家的 $$$1$$$ 增加到最右边玩家的 $$$n$$$。每个玩家都有一个预先选择的形状,他们将在整个锦标赛的每场比赛中使用该形状。比赛的进行方式如下:
- 如果只剩下一名玩家,则宣布他为冠军。
- 否则,任意选择该行中的两个相邻玩家,并进行下一场比赛。失败的玩家将从锦标赛中被淘汰,并离开他在该行中的位置(与他的前邻居相邻)。如果比赛是平局,则通过掷硬币决定输家。
组织者了解所有玩家最喜欢的形状。他们希望找出有机会成为锦标赛冠军的玩家总数(即有合适的方法来选择游戏顺序并操纵抛硬币)。不过,一些玩家仍在优化他们的策略,并可以向组织者通报他们的新形状。在每次这样的请求之后,你能找到可能的冠军数量吗?
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ - 分别表示玩家数量和请求数量 ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq q \leq 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 个字符的字符串。如果玩家 $$$i$$$ 在所有请求之前分别要玩“石头”、“布”或“剪刀”,则这些字符中的第 $$$i$$$ 是“R”、“P”或“S”。
以下 $$$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$$$ 请求后可能出现的冠军数量。
示例
输入 #1
3 5 RPS 1 S 2 R 3 P 1 P 2 P
输出 #1
2 2 1 2 2 3