题目背景

出题人也想写有趣的题目背景。

题目描述

小 D 有一个长度为 $n$ 的序列 $a$，第 $i$ 个位置上的值为 $a_i$。现有 $m$ 个操作：

1. 1 p x ，小 D 令 $a_p = x$。
2. 2 l r x ，小 D 让 $[l,r]$ 内的所有值异或上 $x$，即 $ \forall i \in [l,r] ,a_i=a_i \operatorname{xor} x $。
3. 3 l r x ，小 D 让 $[l,r]$ 内的所有值或上 $x$，即 $\forall i \in [l,r] ,a_i=a_i \operatorname{or} x$。
4. 4 l r x ，小 D 让 $[l,r]$ 内的所有值与上 $x$，即 $ \forall i \in [l,r] ,a_i=a_i \operatorname{and} x $。
5. 5 l r ，小 D 想让你帮他求 $[l,r]$ 内所有子区间的异或和的和，即 $ \sum_{i=l}^r \sum_{j=i}^r \operatorname{xor}_{k=i}^j a_k $。

输入格式

第一行两个正整数 $n,m$。

第二行有 $n$ 个非负整数，第 $i$ 个数为 $a_i$。

接下来 $m$ 行，每行有 $3$ 到 $4$ 个非负整数，描述一个操作。格式见题目描述。

输出格式

对于每个操作 $5$ ，输出一行一个非负整数表示答案。

样例1输入

8 8
1 9 2 6 0 8 1 7
5 1 5
5 4 7
1 5 1
5 2 3
2 4 6 4
1 5 5
2 6 8 5
5 5 7

样例1输出

111
76
22
51

样例2输入

8 10
1 0 3 3 4 3 7 4 
2 5 7 6
3 5 6 3
5 1 2
1 7 3
1 1 4
4 2 7 7
5 3 4
2 2 3 7
4 6 8 3
5 7 8

样例2输出

2
6
6

为了选手更好的做题体验，我们提供了很大很大的样例，祝大家做题愉快。

数据范围

对于所有的数据，有 $ 2 \leq n,m \leq 10^5 ,0 \leq a_i,x < 2^{29}, 1 \leq l \leq r \leq n,1 \leq p \leq n $。