Keen Kena Googler the Keener was keen to try out some queries on the new multiset he got for his birthday, until he realized that he seemed to be getting incorrect answers for his queries. Thus, he decided to write a program that simulates the queries he's trying to perform on the multiset. However, his program wasn't very efficient, and he hopes that you might be able to help him write a better one.

His multiset supports the following queries (Note: ~a \oplus b~ denotes the bitwise XOR operation between ~2~ integers ~a~ and ~b~):

• 1 x: Insert the integer ~x~ into the multiset.
• 2 l r x: For every integer ~a~ in the multiset where ~l \le a \le r~, replace it with ~a \oplus x~.
• 3 l r: Let ~a_1, a_2, \dots, a_k~ be all integers in the multiset where ~l \le a_i \le r~. Output the value ~a_1 \oplus a_2 \oplus \dots \oplus a_k~.

Write a program that can support ~Q~ queries of the above types.

Constraints

For all subtasks:

~1 \le N, Q \le 2 \times 10^5~

~0 \le a_i, x \le 2 \times 10^5~

~0 \le l \le r \le 5 \times 10^5~

Subtask 1 [1/15]

~1 \le N, Q \le 2\,000~

Subtask 2 [2/15]

There will be no operations of the type 2 l r x.

Subtask 3 [4/15]

For all operations of the type 2 l r x, ~l = 0~ and ~r = 5 \times 10^5~.

Subtask 4 [8/15]

No additional constraints.

Input Specification

The first line will contain two integers, ~N~ and ~Q~.

The next line will contain ~N~ space-separated integers, the initial elements of Keen Kena Googler the Keener's multiset.

The next ~Q~ lines will each contain a query of one of the above three types.

Output Specification

For each query of type ~3~, output its answer on a separate line.

Sample Input

2 3
1 2
2 0 3 4
3 2 9
3 5 5

Sample Output

3
5

Sample Explanation

Our initial multiset contains ~\{1, 2\}~. After our first operation, we have ~\{5, 6\}~. The first type ~3~ operation outputs ~5 \oplus 6 = 3~ while the second one outputs ~5=5~.