题目描述

AKN 觉得第一题太水了，不屑于写第一题，所以他又玩起了新的游戏。在游戏中，他发现，这个游戏的伤害计算有一个规律，规律如下：

1. 拥有一个伤害串，是一个长度为 $n$ 的只含字符 0 和字符 1 的字符串。规定这个字符串的首字符是第一个字符，即下标从 $1$ 开始。
2. 给定一个范围 $[l, r]$，伤害为伤害串的这个范围内中字符 1 的个数。
3. 会修改伤害串中的数值，修改的方法是把 $[l, r]$ 中所有原来的字符 0 变成 1，将 1 变成 0。

AKN 想知道一些时刻的伤害，请你帮助他求出这个伤害。

输入格式

输入的第一行有两个用空格隔开的整数，分别表示伤害串的长度 $n$，和操作的个数 $m$。

输入第二行是一个长度为 $n$ 的字符串 $S$，代表伤害串。

第 $3$ 到第 $(m + 2)$ 行，每行有三个用空格隔开的整数 $op, l, r$。代表第 $i$ 次操作的方式和区间，规则是：

• 若 $op = 0$，则表示将伤害串的 $[l, r]$ 区间内的 0 变成 1，1 变成 0。
• 若 $op = 1$，则表示询问伤害串的 $[l, r]$ 区间内有多少个字符 1。

输出格式

对于每次询问，输出一行一个整数，代表区间内 1 的个数。

样例

10 6
1011101001
0 2 4
1 1 5
0 3 7
1 1 10
0 1 4
1 2 6

3
6
1

样例解释

原伤害串为 1011101001。

• 第一次操作，改变 $[2, 4]$ 的字符，伤害串变为 1100101001。
• 第二次操作，查询 $[1, 5]$ 内 1 的个数，共有 $3$ 个。
• 第三次操作，改变 $[3, 7]$ 的字符，伤害串变为 1111010001。
• 第四次操作，查询 $[1, 10]$ 内 1 的个数，共有 $6$ 个。
• 第五次操作，改变 $[1, 4]$ 的字符，伤害串变为 0000010001。
• 第六次操作，查询 $[2, 6]$ 内 1 的个数，共有 $1$ 个。

数据范围与提示

• 对于 $10\%$ 的数据：$n, m \leq 10$。
• 另有 $30\%$ 的数据：$n, m \leq 2 \times 10^3$。
• 对于 $100\%$ 的数据：$2 \leq n, m \leq 2 \times 10^5$，$0 \leq op \leq 1$，$1 \leq l \leq r \leq n$，$S$ 中只含字符 0 和字符 1。