题目描述

一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 $n + 1$ 个停车站点，它们将街道划分成了 $n$ 条路段。每一路段都拥有一个路灯。当第 $i$ 个路灯亮起，它将照亮连接第 $i$ 与第 $i + 1$ 个站点的路段。否则这条路段将是黑暗的。

安全起见，出租车只能在被照亮的路段上行驶。换言之，出租车能从站点 $a$ 出发到达站点 $b$ $(a < b)$ 的条件是：连接站点 $a$ 与 $a + 1$，$a + 1$ 与 $a + 2$，……，$b - 1$ 与 $b$ 的路段都被照亮。

在经过一些意外故障或修理之后，街道上的路灯可能是亮起的，也可能是熄灭的。

现在给定 $0$ 时刻时，街道上路灯的初始状态。之后 $1, 2,\ldots, q$ 时刻，每时刻会发生下列两种事件之一：

• toggle $i$：切换第 $i$ 个路灯的状态。具体地说，若路灯原来亮起，则现在将熄灭；若路灯原来熄灭，则现在将亮起。
• query $a$ $b$：出租车部门的负责人想知道，从 $0$ 时刻起到当前时刻，有多少个时刻满足：出租车能够从站点 $a$ 出发到达站点 $b$。

请你帮助出租车部门的负责人回答他们的问题。

---

输入格式

第一行包含两个整数 $n$ 和 $q$——表示路灯的数量与时刻数。

第二行包含一个字符串 $s$ 表示路灯的初始状态，$s_i$ 为 1 表示第 $i$ 个路灯初始时亮起；$s_i$ 为 0 表示第 $i$ 个路灯初始时熄灭。

接下来 $q$ 行每行描述一个时刻的事件。第 $i$ 行描述时刻 $i$ 所发生的事件：

• toggle $i$：该时刻切换了第 $i$ 个路灯的状态。
• query $a$ $b$：计算从 $0$ 时刻起到该时刻，共有多少个时刻满足：出租车能从站点 $a$ 出发到达站点 $b$。

至少有一个时刻的事件是 query。

---

输出格式

对于每个 query 的事件，输出一行单个整数，表示该问题的答案。

---

样例

样例 1

输入

5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

输出

1
2
0
0
1
2

说明

在这组样例中：

时刻	路灯状态	询问	答案对应的时刻
0	11011	-
1		query $1$ $2$	1
2			1, 2
3		query $1$ $6$	无
4		query $3$ $4$
5		toggle $3$	-
6	11111	query $3$ $4$	6
7		query $1$ $6$	6, 7

解释：

• 时刻 1：查询站点 1 到 2，只需要路灯 1 亮起，当前时刻 1 满足，共 1 个时刻。
• 时刻 2：查询站点 1 到 2，时刻 1 和 2 都满足，共 2 个时刻。
• 时刻 3：查询站点 1 到 6，需要路灯 1, 2, 3, 4, 5 全部亮起，但路灯 3 和 5 熄灭，无满足的时刻。
• 时刻 4：查询站点 3 到 4，需要路灯 3 亮起，但当前路灯 3 熄灭，无满足的时刻。
• 时刻 5：切换路灯 3 的状态，从 0 变为 1。
• 时刻 6：查询站点 3 到 4，需要路灯 3 亮起，时刻 6 满足，共 1 个时刻。
• 时刻 7：查询站点 1 到 6，需要路灯 1, 2, 3, 4, 5 全部亮起，时刻 6 和 7 满足，共 2 个时刻。

---

数据范围与提示

对于全部数据，$1 \le n, q \le 3 \times 10^5$，$|s| = n$，$1 \le i \le n$，$1 \le a < b \le n + 1$。

详细子任务限制与分值如下表。

子任务	附加限制	分值
1	$n, q \le 100$	20
2	对于所有 query $a$ $b$ 事件，满足 $b - a = 1$
3	对于所有 toggle $i$ 事件，第 $i$ 个路灯将被点亮
4	所有 toggle 事件都发生在第一个 query 事件之前
5	无特殊限制