[Ynoi2014] 人人本着正义之名

题目背景

那是什么? 【不是第六兽,是新的兽?】 【我从来没见过那种玩意啊】 ![](https://cdn.luogu.com.cn/upload/pic/45515.png) 【全员退避】 【现已确认出现预料之外的兽】 【根据这一事态,将作战确认为失败,放弃15号岛】 怎么会... ![](https://cdn.luogu.com.cn/upload/pic/45516.png) 我和他约好了的 绝对要活着回去 ![](https://cdn.luogu.com.cn/upload/pic/45517.png) 对他说“我回来了”,然后品尝黄油蛋糕 所以,要是世界终结的话我会很伤脑筋的 ![](https://cdn.luogu.com.cn/upload/pic/45518.png) 融没于晨雾之中的树林 啊...? ![](https://cdn.luogu.com.cn/upload/pic/45519.png) 【牛奶迹.耀眼花瓣.狂风气团】 【挂于墙上的鲱鱼.倒立的刺猬.袋中的风琴】 这是什么...? ![](https://cdn.luogu.com.cn/upload/pic/45520.png) 你其实...很想战斗的对吧 虽然我不知道你有什么打算,但是已经够了 ![](https://cdn.luogu.com.cn/upload/pic/45521.png) 你已经不用战斗了 因为你的战斗,已经由我,由我们继承下来了 【其实我很感激你】 【一直以来,我心里就只想着死】 ![](https://cdn.luogu.com.cn/upload/pic/45523.png) 【渴望去往那些等着我回去的家伙身边,这是我唯一的愿望】 【但是遇见你们之后,我有了一些改变】 【我又开始渴望获得一个容身之处了】 【遇见你之后,我得到了一些救赎】 【能够等到你平安归来,我现在...】 【嗯,可以说,感受到了一丝幸福】 啊...? ![](https://cdn.luogu.com.cn/upload/pic/45524.png) 【不...等一下,你别这么露骨地和我拉开距离啊】 【也别露出一副“这个不知廉耻的生物是怎样”的表情啊】 【不过话说回来,你观察我观察地很仔细啊】 哈哈... 因为喜欢上了嘛~ ![](https://cdn.luogu.com.cn/upload/pic/45525.png) ![](https://cdn.luogu.com.cn/upload/pic/45526.png) 【由不得我啊】 你要去的话我会生气的,我会大发雷霆的 【珂朵莉...】 ![](https://cdn.luogu.com.cn/upload/pic/45527.png) 【对不起】 ![](https://cdn.luogu.com.cn/upload/pic/45528.png) 我等你 ![](https://cdn.luogu.com.cn/upload/pic/45529.png) 我会等着你的,所以一定要回来哦 ![](https://cdn.luogu.com.cn/upload/pic/45530.png) 【我保证,一定会回来的】 嗯 说好了哦~ ![](https://cdn.luogu.com.cn/upload/pic/45531.png)

题目描述

你需要帮珂朵莉维护一个长为 $n$ 的 `01`序列 $a$,有 $m$ 个操作: - `1 l r`:把区间 $[l,r]$ 的数变成 $0$。 - `2 l r`:把区间 $[l,r]$ 的数变成 $1$。 - `3 l r`:$[l,r-1]$ 内所有数 $a_i$,变为 $a_i$ 与 $a_{i+1}$ 按位或的值,这些数同时进行这个操作。 - `4 l r`:$[l+1,r]$ 内所有数 $a_i$,变为 $a_i$ 与 $a_{i-1}$ 按位或的值,这些数同时进行这个操作。 - `5 l r`:$[l,r-1]$ 内所有数 $a_i$,变为 $a_i$ 与 $a_{i+1}$ 按位与的值,这些数同时进行这个操作。 - `6 l r`:$[l+1,r]$ 内所有数 $a_i$,变为 $a_i$ 与 $a_{i-1}$ 按位与的值,这些数同时进行这个操作。 - `7 l r`:查询区间 $[l,r]$ 的和。 本题强制在线,每次的 $l,r$ 需要与上次答案做 $\operatorname{xor}$ 运算,如果之前没有询问,则上次答案为 $0$。

输入输出格式

输入格式


第一行两个整数表示 $n$ 和 $m$。 第二行 $n$ 个整数表示序列 $a$。 之后 $m$ 行,每行三个整数 $opt,l,r$,表示是哪一种操作以及操作对应的区间。

输出格式


对于每个查询操作输出一行一个数表示答案。

输入输出样例

输入样例 #1

5 5
0 1 0 0 1
3 2 5
5 2 5
2 2 2
6 1 5
7 1 5

输出样例 #1

1

说明

Idea:nzhtl1477,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477 序列每次的样子: $$0\ 1\ 0\ 0\ 1$$ $$0\ 1\ 0\ 1\ 1$$ $$0\ 0\ 0\ 1\ 1$$ $$0\ 1\ 0\ 1\ 1$$ $$0\ 0\ 0\ 0\ 1$$ $$0\ 0\ 0\ 0\ 1$$ 对于 $30\%$ 的数据,$n,m\leq 1000$。 对于 $50\%$ 的数据,$n,m\leq 10^5$。 对于另外 $30\%$ 的数据,操作和序列均随机生成。 对于另外 $10\%$ 的数据,$n,m\leq 10^6$。 对于 $100\%$ 的数据,$1\leq n,m\leq 3 \times 10^6$,$0\leq a_i\leq 1$。