E. LOL
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

一个长度为 $$$n$$$，只含字母 $$$L$$$ 和 $$$O$$$ 组成的字符串 $$$S~=~s_1~s_2~\ldots~s_n$$$ 。定义一个字符串的子序列为将字符串中的若干个字符去掉，得到的字符串。现在，对字符串 $$$S$$$ 进行以下两种操作：

  • 操作 $$$1~l~r$$$，表示输出字符串 $$$s'=s_l,s_{l+1},\ldots,s_r]$$$ 中含多少个子序列 $$$LOL$$$；
  • 操作 $$$2~l~r$$$，表示将字符串 $$$s'=s_l,s_{l+1},\ldots,s_r$$$ 中的 $$$L$$$ 变成 $$$O$$$，$$$O$$$ 变成 $$$L$$$。

请按操作序列依次进行操作，依次输出操作 $$$1$$$ 的结果。

Input

第一行给出 $$$n$$$ 和 $$$t$$$ 分别表示字符串的长度和询问次数。 第二行给出一个长度为 $$$n$$$ 的字符串 $$$S$$$，保证 $$$s$$$ 只由 $$$L,O$$$ 组成。 接下来 $$$t$$$ 行，每行一个操作，包含三个整数，$$$opt,l,r,~(1 \le opt \le 2,1 \le l \le r \le n)$$$。

Output

对于每个 $$$opt$$$ 为 $$$1$$$ 时输出一行，包含一个整数，为对应的结果。

Example
Input
5 5
LOLOL
1 1 5
2 1 5
1 1 5
2 3 5
1 3 5
Output
4
1
1
Note

$$$1 \le n \le 3 \times 10^5,~1 \le t \le 3 \times 10^5$$$