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

1. Given an interval $[l, r]$, XOR all numbers in the interval with $x$.
2. Given an interval $[l, r]$, sort the numbers in the interval in non-decreasing order.
3. Given an interval $[l, r]$, calculate the XOR sum of the numbers in the interval.

Input

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

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

The next $m$ lines each contain three integers $opt, l, r$ (for $opt \in \{2, 3\}$) or four integers $opt, l, r, x$ (for $opt = 1$), representing the corresponding operations.

Output

For each operation of type 3, output one line containing the answer.

Examples

Input 1

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

Output 1

6

Note

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

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

XOR the interval $[2, 4]$ with $5$: $2\ \mathrm{xor}\ 5 = 7$, $4\ \mathrm{xor}\ 5 = 1$, $8\ \mathrm{xor}\ 5 = 13$, resulting in $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$.