当前没有测试数据。

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

2
0

输入 #2复制

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

输出 #2复制

11
0
34
0
11
6

说明/提示

对于 2020% 的数据：1≤�,�≤1001≤n,m≤100，1≤�≤�≤�1≤l≤r≤n； 对于另 2020% 的数据：1≤�≤1≤n≤ 105105，�=1m=1，1≤�≤�≤�1≤l≤r≤n； 对于另 2020% 的数据：1≤�,�≤1≤n,m≤ 105105，�=1,�=�l=1,r=n； 对于 100100% 的数据：1≤�,�≤1≤n,m≤ 55 ×× 105105，1≤�≤�≤�1≤l≤r≤n。

所有数据保证合法。