Problem Description

You are given an integer sequence of length $n$: $a_1$, $a_2$, $\ldots$, $a_n$. You need to support the following two operations. Each operation can be represented by four integers $opt\;l\;r\;v$:

When $opt=1$, it means to xor every number in the interval $[l,r]$ with $v$.

When $opt=2$, query the maximum xor value between $v$ and the xor of any chosen numbers (including choosing $0$ numbers) within the interval $[l,r]$.

Input Format

The first line contains two positive integers $n, m$. The second line contains $n$ integers representing the sequence. Then there are $m$ lines, each containing four integers $opt, l, r, v$, describing an operation.

Output Format

For each operation with $opt=2$, output one line with one integer representing the answer.

4 5
1 14 51 4
2 1 3 0
1 2 3 3
2 1 4 10
1 1 4 514
2 3 4 2

61
63
560

Hint

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

For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^4$, and the values are in $[0,10^9]$.

Translated by ChatGPT 5