来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 20 套，第 3 题。原题标号：C；原本地编号：Z4P1-20-C。

给定一个数列$a$，你需要进行下面三种操作：

1. 求出某区间每一个数的按位异或和。
2. 求出某区间每一个数的按位或和。
3. 求出某区间每一个数的按位与和。

输入格式

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

1. 1 l r：输出区间 $[l, r]$ 内每个数的按位异或和。
2. 2 l r：输出区间 $[l, r]$ 内每个数的按位或和。
3. 3 l r：输出区间 $[l, r]$ 内每个数的按位与和。

输出格式

输出包含 $m$ 行整数，即为所有操作的结果。

样例

5 5
9 9 4 9 1 
1 1 4
1 2 4
2 1 4
3 2 2
1 4 5

13
4
13
9
8

其他样例见下发文件。

数据范围

特殊性质A：只包含一操作。

对于 $100\%$ 的数据：$1 \le n, m \le 5 \times {10}^5$，$0 \le a_i \le 10^6$。