B. Chevonne's Game
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Would you like to play a game with Chevonne?

Chevonne is a kind witch. She has many magic pearls, the color of which is either white or black. The pearls are in a line and numbered from $$$1$$$ to $$$n$$$. Chevonne may change the color of some of the pearls while giving you a number of queries. Anyone who can answer all the queries correctly will be blessed by her and get an "Accepted".

Specifically, Chevonne will perform $$$q$$$ actions in the following two forms:

  • $$$\texttt{M L R }$$$ Chevonne uses the magic to change the color(white to black and black to white) of the pearls with the number from $$$L$$$ to $$$R$$$.
  • $$$\texttt{Q L R }$$$ Chevonne gives you a query about the minimum number of times needed to take away all the pearls with the number from $$$L$$$ to $$$R$$$. You can only take away the pearls in the following way: Select several continuous pearls(the concept of which is similar to sub-string), and every two adjacent pearls of them have different colors (selecting one pearl is always OK). Take away these pearls and merge the remaining pearls(if any) to form a whole.
Input

The first line contains two integers $$$n~(1\leq n \leq 10^6)$$$ and $$$q~(1\leq q \leq 10^6)$$$.

The second line contains a binary string $$$s$$$ of length $$$n$$$, the $$$i$$$th character represents the color of the pearl with the number $$$i$$$($$$0$$$ represents white and $$$1$$$ represents black).

Following comes $$$q$$$ lines. Each line contains one character and two integers $$$L,R~(1\leq L \leq R \leq n)$$$, representing an action Chevonne will perform.

Output

For each query, please print one line of a single number representing the answer of the corresponding query.

Example
Input
8 5
10001101
Q 1 3
Q 1 8
M 3 5
Q 1 3
Q 1 8
Output
2
3
1
2
Note

For the first query, we need to figure out the minimal number of times to take away the first three pearls"100".

The answer is $$$2$$$. A feasible solution is:

1. Take away the first two pearls"10"; 2. Take away the remaining one pearl"0".