Cho một dãy số nguyên gồm ~N~ phần tử ~A_{1}, A_{2}, ..., A_{N}~ và ~Q~ truy vấn. Mỗi truy vấn có một trong 2 dạng sau:

• Dạng ~1~ ~i~ ~x~ : Thao tác này sẽ thay đổi giá trị phần tử ~A_{i}~ thành ~A_{i} = A_{i} \oplus x~
• Dạng ~2~ ~l~ ~r~ : Thao tác này sẽ in ra màn hình giá trị ~A_{l} \oplus A_{l+1} \oplus A{l+2} \oplus ... \oplus A_{r-1} \oplus A_{r}~

Với phép ~\oplus~ là phép xor trong các phép toán thao tác bit trong các ngôn ngữ lập trình.

Yêu cầu với mỗi truy vấn dạng 2 in ra kết quả trên 1 dòng riêng biệt.

Input

• Dòng thứ nhất chứa 2 số nguyên ~N~ và ~Q~
• Dòng thứ hai chứa ~N~ số nguyên ~A_{1}, A_{2}, ..., A_{n}~
• ~Q~ dòng tiếp theo mỗi dòng là các truy vấn dạng 1 hoặc dạng 2

Biết rằng

• ~1 \leq N, Q \leq 10^5~, ~0 \leq A_{i} \leq 10^4~
• Đối với truy vấn dạng ~1~ : ~1 \leq i \leq N~, ~1 \leq x \leq 10^4~
• Đối với truy vấn dạng ~2~ : ~1 \leq l \leq r \ leq N~

Output

In rakết quả của các truy vấn dạng ~2~. Mỗi kết quả ghi trên 1 dòng.

Sample

Input #1

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

Output #1

0
1
2