Given a sequence $a$ of $n$ non-negative integers, perform $q$ operations, where each operation is one of the following three types:

• 1: Simultaneously update $a_i \leftarrow a_i \oplus a_{i+1}$ for all $i \in [1, n)$.
• 2: Simultaneously update $a_i \leftarrow a_i \oplus a_{i-1}$ for all $i \in (1, n]$.
• 3 l r: Calculate $\bigoplus_{i=l}^r a_i$.

Input

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

The second line contains $n$ non-negative integers, representing the sequence $a$.

The next $q$ lines each contain one or three positive integers, representing an operation.

Output

For each operation of type 3, output one number per line representing the answer.

Examples

Input 1

5 5
1 4 5 2 6
1
3 2 4
2
3 2 4
3 1 1

Output 1

2
1
5

Input 2

9 7
0 3 1 4 1 5 9 2 6
1
2
2
3 1 6
1
3 2 5
3 3 9

Output 2

8
11
6

Constraints

For all test cases, it is guaranteed that:

• $1 \le n \le 3 \times 10^5$
• $1 \le q \le 3 \times 10^5$
• $0 \le a_i < 2^{30}$

This problem uses bundled testing. The special properties of each subtask are as follows:

Special Property A: No operation 2.

Special Property B: The number of type 3 operations does not exceed one.