Description

给定一个长度为 $n$ 字符串 $S$ ，同时进行 $m$ 次操作：
操作1：$1$ $x$ $c$ 表示将第 $x$ 个字符改为 $c$（ $c$ 只会为 I 或 O ）。
操作2：$2$ $l$ $r$ 询问字符串 $S$ 中有多少对三元组 $(i,j,k)$ 满足：
$S_{i}=$ I ,$S_{j}=$ O ,$S_{k}=$ I 并且 $l≤i<j<k≤r$ 。

Input Format

输入第一行两个正整数 $n$ 和 $m$ 。
接下来一行是长度为 $n$ 的字符串 $s$ ，接下来 $m$ 行是操作。
含义均如题。

Output Format

输出若干行：对于所有操作2，输出查询的答案，要求每个答案之间换行。

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

对于 $20$% 的数据：$1 ≤ n,m ≤ 100$，$1 ≤ l ≤ r ≤ n$；
对于另 $20$% 的数据：$1 ≤ n ≤$ $10^{5}$，$m = 1$，$1 ≤ l ≤ r ≤ n$；
对于另 $20$% 的数据：$1 ≤ n,m ≤$ $10^{5}$，$l=1,r=n$；
对于 $100$% 的数据：$1 ≤ n,m ≤$ $5$ $\times$ $10^{5}$，$1 ≤ l ≤ r ≤ n$。

所有数据保证合法。