双人游戏

写完论文的莲子终于意识到了这么多天埋头写论文而不理会梅莉的错误，并打算约梅莉出来玩。为此，她构思了一个有趣的双人游戏。

莲子构思了一个双人游戏，不妨令游戏的两个玩家为小 R 和小 M，规则如下： 有一个 $1\times n$ 的棋盘。初始时，棋盘上有一些黑色棋子，一些白色棋子，和 $m$ 个空格子。我们可以用一个长度为 $n$ 的字符串 $s$ 来描述初始时的棋盘，若 $s_i$ 为 `B` 则代表该位置为黑棋子，为 `W` 则代表白棋子，为 `_` 则代表空格子。**请注意，棋盘上可能没有空格子。** 游戏开始前，除了棋盘的初始状态，两人还会获得一个操作序列 $O=[\lang c_1,x_1\rang, \lang c_2,x_2\rang, \cdots,\lang c_m,x_m\rang]$，其中二元组 $\lang c_i,x_i\rang$ 满足 $c_i\in\{\mathtt{R}, \mathtt{M}\}$ 且 $x_i$ 位置此时是一个空格子，表示在第 $i$ 步，玩家小 $c_i$ 应该在 $x_i$ 位置放上一个黑色棋子或者白色棋子。序列 $O$ 对双方公开，也就是说双方均知道每一步是由谁在哪个位置放上一枚棋子。 游戏过程中，双方会按照该操作序列进行操作。第 $i$ 轮时小 $c_i$ 在 $x_i$ 位置放置一枚棋子，棋子的颜色由该玩家决定。在游戏结束时所有格子都被放上了恰好一枚棋子。 小 R 希望游戏结束后棋子组成的**极长同色连续段数**$^*$尽可能多，而小 M 则希望其尽可能少。试着求出两人都以最优方式摆放棋子的话最后的连续段数为几。容易证明答案是一个定值。 注：一个棋子的极长同色连续段被定义为一个二元组 $(l,r)$ 满足 $l\le r$，且从左至右数第 $l$ 个棋子到第 $r$ 个棋子颜色相同，且第 $l-1$ 个和第 $r+1$ 个棋子要么不存在，要么与前面所说的棋子颜色不同。

第一行两个整数 $n,m$，其中 $m$ 代表棋盘上的空格子数量。 第二行一个长度为 $n$ 的字符串 $s$，描述棋盘的每个格子的状态。 对于接下来的 $m$ 行：第 $i$ 行一个字符 $c_i$ 和一个正整数 $x_i$，描述第 $i$ 回合操作的玩家和她放置棋子的位置。

输出一行一个整数，表示两人都以最优方式摆放棋子的话最后的连续段数为几。

3 2
B__
R 3
M 2

2

3 3
___
R 1 
R 3
M 2

2

5 2
BW__B
R 4
R 3

5

### 样例解释 #### 样例 \#1 最终的棋子摆放结果为 `BWW`，可以证明两人这样摆均为最优。极长连续段数为 $2$。 #### 样例 \#2 为了让连续段数尽可能大，先手摆放两个空格子的小 R 一定会让两个格子的棋子颜色不同。然后小 M 会放置一个任意颜色的棋子。有多种可能的最终摆放结果，其中一种为 `BWW`，极长连续段数为 $2$。 注意到该样例符合特殊性质 $\mathbf{B}$。 #### 样例 \#3 最终的棋子摆放结果为 `BWBWB`，极长连续段数为 $5$。 注意到该样例符合特殊性质 $\mathbf{A}$。 ### 数据范围 **本题采用捆绑测试。** $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n,m\le } & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline 1 & 10 & 20 & - &-\cr\hline 2 & 10 & 2\times 10^5 & \mathbf{A}&- \cr\hline 3 & 20 & 2\times 10^5 & \mathbf{B}&- \cr\hline 4 & 20 & 10^3 & -&1 \cr\hline 5 & 40 & 2\times 10^5 & -&1,2,3,4 \cr\hline \end{array} $$ 特殊性质 $\mathbf{A}$：保证要么 $c_i$ 均为 $\tt R$，要么 $c_i$ 均为 $\tt M$。\ 特殊性质 $\mathbf{B}$：保证 $s$ 中所有字母均为 $\tt \_$。 对于所有数据满足：$\red0\le m\le 2\times 10^5 $，$1\le n\le 2\times 10^5$，且有 $m\le n$，$s_i\in \{\tt{B,W,\_}\}$。