Cow Land là một công viên giải trí đặc biệt dành cho bò, nơi chúng đi dạo, ăn cỏ ngon, và ghé thăm các điểm tham quan khác nhau dành cho bò (tàu lượn roller cowster đặc biệt phổ biến).

Có tổng cộng \(N\) điểm tham quan khác nhau \((2 \le N \le 10^5)\). Một số cặp điểm tham quan được kết nối bằng những con đường, tổng cộng \(N - 1\) con đường, sao cho có duy nhất một tuyến đường bao gồm các con đường khác nhau giữa bất kỳ hai điểm tham quan nào. Mỗi điểm tham quan \(i\) có một giá trị niềm vui là \(e_i\), giá trị này có thể thay đổi trong suốt cả ngày, vì một số điểm tham quan trở nên hấp dẫn hơn vào buổi sáng và một số khác vào buổi chiều.

Một con bò đi từ điểm tham quan \(i\) đến điểm tham quan \(j\) sẽ trải nghiệm tất cả các điểm tham quan trên tuyến đường từ \(i\) đến \(j\). Điều đặc biệt là tổng giá trị niềm vui của toàn bộ tuyến đường này được tính bằng \(XOR\) bitwise của tất cả các giá trị niềm vui dọc theo tuyến đường, bao gồm cả điểm bắt đầu \(i\) và điểm kết thúc \(j\).

Vui lòng giúp những chú bò xác định giá trị niềm vui của các tuyến đường mà chúng dự định sử dụng trong chuyến đi tiếp theo đến Cow Land.

Dữ liệu vào

• Dòng đầu tiên của đầu vào chứa \(N\) và số lượng truy vấn \(Q\) \((1 \le Q \le 10^5)\).
• Dòng tiếp theo chứa \(e_1, e_2, ..., e_N\) (giá trị niềm vui của từng điểm tham quan, \(0 \le e_i \le 10^9\)).
• \(N - 1\) dòng tiếp theo mỗi dòng mô tả một con đường giữa hai điểm tham quan dưới dạng hai số nguyên \(a\) và \(b\) (cả hai nằm trong khoảng \(1...N\)).
• \(Q\) dòng cuối mô tả hoặc là một cập nhật cho một trong các giá trị \(e_i\) hoặc là một truy vấn về giá trị niềm vui của một tuyến đường.
• Một dòng dưới dạng "1 i v" có nghĩa là \(e_i\) cần được cập nhật thành giá trị \(v\).
• Một dòng dưới dạng "2 i j" là một truy vấn để tính giá trị niềm vui của tuyến đường nối hai điểm tham quan \(i\) và \(j\).

Dữ liệu ra

• Với mỗi truy vấn dạng "2 i j", in ra trên một dòng giá trị niềm vui của tuyến đường từ \(i\) đến \(j\).

Input 1

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

Output 1

21
20
4
20