7月28日，今天是阳光明媚的一天。

我提着行李，来到这座岛屿。一切都是如此的熟悉，是我实际上已经来过无数次了吗？

顺着弯弯曲曲的街道，我来到一座普普通通的民房。我知道，这里有我想见的人。

我曾经让她背负了太多太多。但直到失去，我才明白这一切。

我眼前飞过一只七彩的蝴蝶，它们的翅膀上散发着模糊的光芒。我是它们的一员吗？

屋里没有人。我打开房门，我看到地上有一本绘画日记。我打开它，一瞬间我想起了某人曾经说过的一句话：“这本日记是魔法的日记，在上面画的东西全都可以实现哦！”

我微微一笑，合上了日记。“umi，我等着你。”

给出一棵线段树，这个线段树是广义线段树。在正常的线段树中，对于区间$[l,r]$，我们会取$m=\lfloor \frac{l+r}{2}\rfloor$，然后将这个区间分成 $[l,m]$ 和 $[m+1,r]$ 两个子区间。在广义的线段树中，$m$ 不要求恰好等于区间的中点，但是 $m$ 还是必须 满足 $l\le m<r$ 的。不难发现在广义的线段树中，树的深度可以达到 $O(n)$ 级别。

如下就是一棵广义线段树：

我们使用先序遍历给出该线段树每个节点的分界点，比如下列序列表示的就是该线段树：

5 1 3 2 4

表示的是$[1,6]$分界点为$5$,$[1,5]$的分界点为$1$，$[2,5]$的分界点为3等

已知这棵线段树的每个节点的值为他所代表的区间数的与。现在你需要支持如下操作：

1 l r x 表示将[l,r]的数都和x做与运算，并更新线段树
2 l r x 表示将[l,r]的数都和x做或运算，并更新线段树
3 l r x 表示将[l,r]的数都和x做异或运算，并更新线段树

保证$[l,r]$一定是线段树上某个节点代表的区间。

4 l r 询问从代表[l,r]的节点开始走，设当前节点的值为y，那么如果y在二进制下的表示中有奇数个1（即popcount(y)%2==1），向当前节点的左儿子走；否则向当前节点的右儿子走。走到不能走为止。输出经过的节点值的和

输入格式

第一行输入正整数$n,q$，表示这棵线段树维护的序列长为$n$，即该线段树有$2n-1$个点，有$q$个操作。

接下来输入$n$个正整数$a_i$表示这个序列的初始值

接下来输入这棵线段树

接下来$q$行，每行输入4个数或3个数，表示操作

输出格式

对于每个询问，输出答案

样例一

input

10 20
0 5 2 10 6 6 12 2 8 7
2 1 9 7 3 4 5 6 8
1 1 10 12
1 5 7 5
4 7 7
4 4 7
3 4 4 15
3 1 1 9
4 1 2
4 1 10
1 1 1 2
3 5 5 5
2 8 9 7
2 2 2 7
3 3 3 12
1 1 2 7
1 9 9 3
4 9 9
3 6 6 14
2 1 1 6
3 6 7 3
4 3 10

output

4
8
4
4
3
4

限制与约定

子任务1(10pts) $n,q\le {10}^3$

子任务2(20pts) $n,q\le {10}^5$，没有修改操作

子任务3(30pts) $n,q\le {10}^5$，没有异或操作

子任务4(40pts) $n\le {10}^6,q\le {10}^5$，无特殊性质

对于所有数据，$a_i,x\le [0,{10}^9]$，保证给出的区间一定是线段树上某个节点所代表的。

时间限制：$4\mathtt{s}$

空间限制：$512\mathtt{MB}$

下载

样例数据下载