Background

After finishing her thesis, Ren finally realized the mistake of neglecting Mei for so many days while engrossed in writing her thesis, and decided to invite Mei to play a game. To this end, she conceived an interesting two-player game.

Problem Description

Ren has devised a two-player game, let's call the two players Xiao R and Xiao M. The rules are as follows:

There is a $1 \times n$ chessboard. Initially, the board contains some black pieces, some white pieces, and $m$ empty spaces. We can describe the initial state of the board with a string $s$ of length $n$, where $s_i$ being B means the position has a black piece, W means a white piece, and _ means an empty space. Note that there may be no empty spaces on the board.

Before the game starts, in addition to the initial state of the board, both players will receive an operation sequence $O = [\langle c_1, x_1 \rangle, \langle c_2, x_2 \rangle, \cdots, \langle c_m, x_m \rangle]$, where the pair $\langle c_i, x_i \rangle$ satisfies $c_i \in \{\mathtt{R}, \mathtt{M}\}$ and $x_i$ is an empty space, indicating that in the $i$-th step, player Xiao $c_i$ should place a black or white piece at position $x_i$. The sequence $O$ is public to both players, meaning both know which player places a piece at which position in each step.

During the game, both players will follow this operation sequence. In the $i$-th round, Xiao $c_i$ places a piece at position $x_i$, and the color of the piece is decided by the player. By the end of the game, exactly one piece is placed on each square.

Xiao R wants the number of maximal same-color contiguous segments to be as high as possible, while Xiao M wants it to be as low as possible. Try to determine the number of contiguous segments if both players place pieces optimally. It is easy to prove that the answer is a fixed value.

Note: A maximal same-color contiguous segment of pieces is defined as a pair $(l, r)$ such that $l \leq r$, and the pieces from the $l$-th to the $r$-th are of the same color, and either the $(l-1)$-th and $(r+1)$-th pieces do not exist, or they are of a different color from the pieces mentioned.

Input Format

The first line contains two integers $n, m$, where $m$ represents the number of empty spaces on the board.

The second line contains a string $s$ of length $n$, describing the state of each square on the board.

For the next $m$ lines: the $i$-th line contains a character $c_i$ and a positive integer $x_i$, describing the player for the $i$-th round and the position where she places the piece.

Output Format

Output a single integer, representing the number of contiguous segments if both players place pieces optimally.

Sample Input and Output

Sample Input #1

3 2
B__
R 3
M 2

Sample Output #1

2

Sample Input #2

3 3
___
R 1 
R 3
M 2

Sample Output #2

2

Sample Input #3

5 2
BW__B
R 4
R 3

Sample Output #3

5

Notes/Hints

Sample Explanation

Sample #1

The final piece arrangement is BWW. It can be proven that this is optimal for both players. The number of maximal contiguous segments is $2$.

Sample #2

To maximize the number of contiguous segments, Xiao R, who places pieces in the two empty spaces first, will ensure the colors of the pieces in these two spaces are different. Then Xiao M will place a piece of any color. There are multiple possible final arrangements, one of which is BWW, with the number of maximal contiguous segments being $2$.

Note that this sample satisfies special property $\mathbf{B}$.

Sample #3

The final piece arrangement is BWBWB, with the number of maximal contiguous segments being $5$.

Note that this sample satisfies special property $\mathbf{A}$.

Data Range

This problem uses batched testing.

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{Points} & \bm{n,m\le } & \textbf{Special Properties} & \textbf{Subtask Dependencies} \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} $$

Special property $\mathbf{A}$: Guarantees that either all $c_i$ are $\tt R$ or all $c_i$ are $\tt M$.
Special property $\mathbf{B}$: Guarantees that all characters in $s$ are _.

For all data, it is guaranteed that $0 \le m \le 2 \times 10^5$, $1 \le n \le 2 \times 10^5$, and $m \le n$, with $s_i \in \{\tt{B, W, _}\}$.

见题面 Input 部分

见题面 Output 部分