Description

Renko has designed a two-player game with two players, Little R and Little M, following these rules:

There is a $1 \times n$ chessboard. Initially, the board has some black pieces, white pieces, and $m$ empty cells. The initial state of the board is described by a string $s$ of length $n$, where:

• B indicates a black piece,
• W indicates a white piece,
• _ indicates an empty cell.
  Note: The board may have no empty cells.

Before the game starts, both players receive an operation sequence $O = [\langle c_1, x_1 \rangle, \langle c_2, x_2 \rangle, \ldots, \langle c_m, x_m \rangle]$, where each pair $\langle c_i, x_i \rangle$ satisfies:

• $c_i \in \{\mathtt{R}, \mathtt{M}\}$,
• $x_i$ is an empty cell at step $i$.

This sequence is public, meaning both players know who will place a piece and where at each step.

During the game, players follow the operation sequence. In the $i$-th step, player $c_i$ places a piece (black or white, chosen by the player) at position $x_i$. By the end of the game, every cell will have exactly one piece.

Little R aims to maximize the number of maximal consecutive monochromatic segments$^*$, while Little M aims to minimize it. Determine the final number of segments when both play optimally. It can be proven that the answer is unique.

Definition: A maximal consecutive monochromatic segment is a pair $(l, r)$ where $l \leq r$, such that:

• All pieces from the $l$-th to $r$-th position are the same color.
• The $(l-1)$-th piece (if exists) and the $(r+1)$-th piece (if exists) are of a different color.

Input Format

• The first line contains two integers $n$ and $m$, where $m$ is the number of empty cells.
• The second line contains a string $s$ of length $n$, describing the initial board state.
• The next $m$ lines each contain a character $c_i$ and an integer $x_i$, describing the player and the position for the $i$-th step.

Output Format

Output one integer: the number of maximal consecutive monochromatic segments when both players act optimally.

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

Hint

Explanation

Sample #1

The final board is BWW, which is optimal for both players. The number of segments is $2$.

Sample #2

Little R (controlling the first two steps) will place different colors to maximize segments. Little M then places any color. One possible final state is BWW with $2$ segments.
This sample satisfies Special Property B.

Sample #3

The final board is BWBWB with $5$ segments.
This sample satisfies Special Property A.

Constraints

Bundled testing is used.

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

• A: All $c_i$ are either R or M.
• B: All characters in $s$ are _.

For all data: $0 \leq m \leq 2 \times 10^5$, $1 \leq n \leq 2 \times 10^5$, $m \leq n$, and $s_i \in \{\mathtt{B}, \mathtt{W}, \mathtt{\_}\}$.

---

Translated by DeepSeek R1