Problem Description

Maintain a sequence $a_1,a_2,a_3,\ldots,a_n$ consisting of $n$ non-negative integers, and support three operations:

1. Given an interval $[l,r]$, apply XOR with $x$ to every number in this interval.
2. Given an interval $[l,r]$, sort the numbers in this interval in non-decreasing order.
3. Given an interval $[l,r]$, compute the XOR sum of the numbers in this interval.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers $a_i$, representing the original sequence.

The next $m$ lines describe the operations. Each line contains three integers $opt,l,r$ ($opt\in\{2,3\}$), or four integers $opt,l,r,x$ ($opt=1$), representing the corresponding operation.

Output Format

For each operation $3$, output one line with the corresponding answer.

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

6

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078&nzhtl1477, Data: ccz181078.

Sample Explanation

The original sequence is $1\ 4\ 2\ 8\ 3$.

Sort the interval $[1,3]$, getting $[1\ 2\ 4]\ 8\ 3$.

Apply bitwise XOR with $5$ to the interval $[2,4]$: $2\ \mathrm{xor}\ 5 = 7$, $4\ \mathrm{xor}\ 5 = 1$, $8\ \mathrm{xor}\ 5 = 13$, getting $1\ [7\ 1\ 13]\ 3$.

Query the XOR sum of the interval $[1,2]$: $[1\ 7]\ 1\ 13\ 3$, $1\ \mathrm{xor}\ 7 = 6$.

Constraints

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

Translated by ChatGPT 5