题目描述

给定 $n$ 个硬币的初始状态，以及 $m$ 次如下类型的操作：

1. $1 \ x \ y$: 将 $[x, y]$ 之间的硬币每隔一个翻转一个，即翻转 $x, x+2, x+4, \cdots, x+2t \ (x+2t \leq y)$；
2. $2 \ x \ y$: 将 $[x, y]$ 之间的硬币每隔两个翻转一个，即翻转 $x, x+3, x+6, \cdots, x+3t \ (x+3t \leq y)$；
3. $3 \ x \ y$: 将 $[x, y]$ 之间的硬币全部翻转；
4. $4 \ x \ y$: 查询 $[x, y]$ 之间正面朝上的硬币个数。

输入格式

输入的第一行包含两个正整数 $n, m$，用一个空格分隔，分别表示硬币数和操作数。

第二行包含 $n$ 个整数 $f_1, f_2, \cdots, f_n$，相邻整数之间使用一个空格分隔，表示每个硬币的初始状态，其中 $f_i = 0$ 表示第 $i$ 个硬币为反面朝上，$f_i = 1$ 表示第 $i$ 个硬币为正面朝上。

接下来 $m$ 行，每行包含三个正整数 $a_i, x_i, y_i$，相邻整数之间使用一个空格分隔，表示一次操作。

输出格式

输出若干行。对于每次查询操作（$4 \ x \ y$），输出一行包含一个整数表示该查询的答案。

5 8
1 0 0 1 0
1 2 3
4 1 5
2 3 5
4 2 5
3 1 5
4 2 3
3 1 4
4 1 5

3
3
0
5

提示

【评测用例规模与约定】

对于 20% 的评测用例，$1 \leq n, m \leq 5000$；

对于另外 20% 的评测用例，$1 \leq n, m \leq 10^5$，且没有 $1 \ x \ y$ 类型的操作；

对于另外 20% 的评测用例，$1 \leq n, m \leq 10^5$，且没有 $2 \ x \ y$ 类型的操作；

对于所有评测用例，$1 \leq n \leq 5 \times 10^5$，$1 \leq m \leq 10^5$，$f_i \in \{0, 1\}$，$a_i \in \{1, 2, 3, 4\}$，$1 \leq x_i \leq y_i \leq n$。