说明

时间限制：2 Sec 内存限制：256 MB 输入文件：mod2.in 输出文件：mod2.out

给定一个长度为 $N$ 的序列 $A = \{a_1,a_2,\dots,a_N\}$。

请依次处理总共 $Q$ 个操作，操作共三种：

- 操作 $1\ l\ r$

  对每个 $i\in[l,r]$，若 $a_i$ 为奇数则替换为 $1$，若为偶数则替换为 $0$。

- 操作 $2\ l\ r\ x$

  对每个 $i\in[l,r]$，令 $a_i \leftarrow a_i + x$。

- 操作 $3\ l\ r$

  输出区间和 $\displaystyle\sum_{i=l}^{r}a_i$。

输入格式

第一行给出两个整数 $N$ 和 $Q$。

第二行给出 $N$ 个整数 $a_1,a_2,\dots,a_N$。

接下来 $Q$ 行，每行描述一个操作。

输出格式

对每个操作 $3$，在一行内输出区间和。

样例

样例 1

5 7
1 2 3 4 5
3 1 5
1 1 5
3 1 5
2 2 4 3
3 1 5
1 1 5
3 1 5

15
3
12
4

数据范围

对于 50% 的数据，$N,Q \le 1000$，$a_i,x \le 1000$。

另有 10% 的数据，没有操作 1。

对于 100% 的数据：$1\le N,Q\le 10^5$，$1\le a_i\le 10^9$。

操作 1 满足：$1\le l\le r\le N$。

操作 2 满足：$1\le l\le r\le N,\ 1\le x\le 10^5$。

操作 3 满足：$1\le l\le r\le N$，操作 3 至少出现一次。