有一个长度为 $n$ 的二进制序列，你需要执行 $q$ 次操作。操作如下：

1. 对于区间 $[\ell, r]$，同时将区间内每一个相邻的 $01$ 对变为 $10$。
2. 对于区间 $[\ell, r]$，同时将区间内每一个相邻的 $10$ 对变为 $01$。
3. 查询区间 $[\ell, r]$ 中 $1$ 的个数。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 2 \cdot 10^6$; $1 \le q \le 2.5 \cdot 10^5$)。 下一行包含一个长度为 $n$ 的二进制字符串：初始的二进制序列。 接下来的 $q$ 行，每行包含三个整数 $t, \ell, r$，表示操作的类型和范围 ($1 \le t \le 3$; $1 \le \ell \le r \le n$)。

输出格式

对于每个类型为 $3$ 的操作，输出一行，包含一个整数，即查询的答案。

样例

样例输入 1

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

样例输出 1

2
1
3
3
4