Cho mảng ~a~ gồm ~n~ số nguyên được đánh số từ ~1~ đến ~n~. Thực hiện ~q~ truy vấn thuộc một trong hai loại sau:

• Loại ~1~ có dạng 1 x y z ~(1 \le x \le y \le n~ ~;~ ~1 \le z \le 2^{30}-1)~: Cập nhật ~a_i = a_i \oplus z~ với mọi ~x \le i \le y~.
• Loại ~2~ có dạng 2 l r ~(1 \le l \le r \le n)~: Tính giá trị biểu thức ~a_l \oplus a_{l+1} \oplus ... \oplus a_r~.

Toán tử ~\oplus~ đại diện cho phép tính xor giữa hai số nguyên dương.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n,q \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên mảng ~a~ ~(1 \le a_i \le 2^{30}-1)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại trên.

Output

• Với mỗi truy vấn loại ~2~, in ra giá trị biểu thức cần tính trên một dòng.

Examples

Sample Input 1

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

Sample Output 1

10
8

Sample Input 2

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

Sample Output 2

1
0
2

Scoring

• Subtask ~1~ ~-~ ~34\%~ số điểm: ~n,q \le 5000~
• Subtask ~2~ ~-~ ~20\%~ số điểm: Không có truy vấn loại ~1~
• Subtask ~3~ ~-~ ~36\%~ số điểm: ~x=y~ với mọi truy vấn loại ~1~
• Subtask ~4~ ~-~ ~10\%~ số điểm: Không có ràng buộc gì thêm