题目描述

维护一个由n个非负整数构成的序列 $a_1,a_2,a_3,\ldots,a_n$，支持三种操作：

1. 给定区间 $[l,r]$，将对应区间内的数异或上 $x$。
2. 给定区间 $[l,r]$，将对应区间内的数从小到大排序。
3. 给定区间 $[l,r]$，求区间内的数的异或和。

输入格式

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

第二行 $n$ 个整数 $a_i$，表示原序列。

接下来 $m$ 行，每行三个整数 $opt,l,r$（$opt\in\{2,3\}$）或四个整数 $opt,l,r,x$（$opt=1$）表示对应的操作。

输出格式

对每个操作 $3$，输出一行，表示对应的答案。

5 3
1 4 2 8 3
2 1 3
1 2 4 5
3 1 2

6

提示

Idea：ccz181078，Solution：ccz181078，Code：ccz181078&nzhtl1477，Data：ccz181078

样例解释

原序列为 $1\ 4\ 2\ 8\ 3$。

将区间 $[1,3]$ 排序，得到 $[1\ 2\ 4]\ 8\ 3$。

将区间 $[2,4]$ 与 $5$ 按位取异或，$2\ \mathrm{xor}\ 5 = 7$，$4\ \mathrm{xor}\ 5 = 1$，$8\ \mathrm{xor}\ 5 = 13$，得到 $1\ [7\ 1\ 13]\ 3$。

查询区间 $[1,2]$ 的异或和，$[1\ 7]\ 1\ 13\ 3$，$1\ \mathrm{xor}\ 7 = 6$。

数据范围

$1 \le n,m \le 10^5$，$0 \le a_i,x<10^8$。