问题描述

给定一个长度为 $n$ 的 01 串 $S$，你有如下两种操作：

• 1 l r，将 $S_{l\sim r}$ 中所有的 $0$ 变成 $1$，$1$ 变成 $0$。
• 2 l r，问将 $S_{l\sim r}$ 中所有字符变成相邻字符均不相同最少需要修改多少次。

输入格式

第一行输入两个正整数 $n,q$。

第二行输入一个长度为 $n$ 的 01 串 $S$。

第三行输入 $q$ 个操作，每个操作的格式如题目描述。

输出格式

对于每个 2 l r 操作，输出一个整数表示答案。

样例输入1

5 5
10101
2 1 5
1 2 3
2 1 5
2 1 3
2 2 3

样例输出1

0
2
1
0

样例输入2

10 10
1100001110
1 4 8
2 5 8
1 8 9
1 1 1
2 2 4
2 10 10
2 5 6
1 7 9
2 3 3
2 4 10

样例输出2

2
0
0
1
0
2

说明

$1\le n,q\le 3\times 10^5,1\le l\le r\le n$，$S$ 仅由 0 和 1 组成。