Background

After finishing her paper, Renko finally realizes her mistake of burying herself in work and ignoring Merry for so long. She decides to invite Merry out and devises an interesting two-player game.

Problem 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