7月28日，今天是阳光明媚的一天。
我提着行李，来到这座岛屿。一切都是如此的熟悉，是我实际上已经来过无数次了吗？
顺着弯弯曲曲的街道，我来到一座普普通通的民房。我知道，这里有我想见的人。
我曾经让她背负了太多太多。但直到失去，我才明白这一切。
我眼前飞过一只七彩的蝴蝶，它们的翅膀上散发着模糊的光芒。我是它们的一员吗？
屋里没有人。我打开房门，我看到地上有一本绘画日记。我打开它，一瞬间我想起了某人曾经说过的一句话：“这本日记是魔法的日记，在上面画的东西全都可以实现哦！”
我微微一笑，合上了日记。“umi，我等着你。”
给出一棵线段树，这个线段树是广义线段树。在正常的线段树中，对于区间$[l,r]$，我们会取$ m=⌊\frac{l+r}{2}⌋$，然后将这个区间分成 $[l,m]$ 和 $[m+1,r]$ 两个子区间。在广义的线段树中，$m$ 不要求恰好等于区间的中点，但是 $m$ 还是必须 满足 $l≤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\leq 10^3$
子任务2(20pts) $n,q\leq 10^5$，没有修改操作
子任务3(30pts) $n,q\leq 10^5$，没有异或操作
子任务4(40pts) $n\leq 10^6,q\leq 10^5$，无特殊性质
对于所有数据，$a_i,x\leq [0,10^9]$，保证给出的区间一定是线段树上某个节点所代表的。
时间限制：$4\mathtt{s}$
空间限制：$512\mathtt{MB}$