P6373 「StOI-1」IOI 计数

蒻 `L_C_A` 想了解一下 `IOI`，可他太菜了，看不懂题目，只会数数。

给定一个长度为 $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 \le i \lt j \lt k \le r$ 。

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

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

对于 $20 \%$ 的数据：$1 \le n, m \le 100$，$1 \le l \le r \le n$； 对于另 $20 \%$ 的数据：$1 \le n \le 10 ^ 5$，$m = 1$，$1 \le l \le r \le n$； 对于另 $20 \%$ 的数据：$1 \le n, m \le 10 ^ 5$，$l = 1, r = n$； 对于 $100 \%$ 的数据：$1 \le n, m \le 5 \times 10 ^ 5$，$1 \le l \le r \le n$。 所有数据保证合法。