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

If $opt=1$, XOR all numbers in the range $[l, r]$ with $v$.

If $opt=2$, query the maximum XOR sum that can be obtained by XORing any subset of numbers (including an empty subset) from the range $[l, r]$ with $v$.

Input

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

The second line contains $n$ integers representing the given sequence.

Each of the following $m$ lines contains four integers $opt, l, r, v$ representing an operation.

Output

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

Examples

Input 1

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

Output 1

61
63
560

Constraints

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

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