Description

Given a string $S$ of length $n$, perform $m$ operations:

Operation 1: $1$ $x$ $c$ means changing the $x$-th character to $c$ (where $c$ is only I or O).

Operation 2: $2$ $l$ $r$ asks how many triples $(i,j,k)$ in the string $S$ satisfy: $S_{i}=$ I, $S_{j}=$ O, $S_{k}=$ I, and $l \le i < j < k \le r$.

Input Format

The first line contains two positive integers $n$ and $m$.

The next line contains a string $s$ of length $n$, and the next $m$ lines contain the operations.

Their meanings are the same as described above.

Output Format

Output multiple lines: for every operation 2, output the answer to the query, with each answer on its own line.

4 3
IOOI
2 1 4
1 1 O
2 1 2

2
0

10 10
IIOOIOIIIO
1 1 I
2 1 7
1 5 O
2 5 9
1 4 I
1 10 I
2 1 10
2 5 10
2 2 8
2 3 9

11
0
34
0
11
6

Hint

Constraints:

For $20$% of the testdata: $1 \le n,m \le 100$, $1 \le l \le r \le n$.

For another $20$% of the testdata: $1 \le n \le 10^{5}$, $m = 1$, $1 \le l \le r \le n$.

For another $20$% of the testdata: $1 \le n,m \le 10^{5}$, $l = 1, r = n$.

For $100$% of the testdata: $1 \le n,m \le 5 \times 10^{5}$, $1 \le l \le r \le n$.

All input is guaranteed to be valid.

Translated by ChatGPT 5