Gần nhà Per mới mở một công viên giải trí, thu hút được rất nhiều người ghé thăm.

Công viên được bố trí gồm ~n~ điểm vui chơi, sẽ có ~n - 1~ con đường nối hai điểm vui chơi nào đó sao cho giữa hai điểm bất kỳ luôn tồn tại đường đi.

Điểm vui chơi ~i~ có điểm thu hút là ~v_i~ (có thể thay đổi được). Độ vui vẻ của một khách đi từ điểm ~i~ đến ~j~ là tổng XOR tất cả các giá trị của nút nằm trên đường đi từ ~i~ tới ~j~.

Chơi đã chán, Per muốn tính thử xem độ vui vẻ của các khách ghé thăm công viên. Nhiệm vụ của cậu là trả lời ~q~ truy vấn thuộc hai loại:

1. Đổi giá trị ở nút ~k~ thành ~x~: ~v_k = x~.
2. Tính độ vui vẻ của đường đi từ ~i~ tới ~j~.

Các bạn cùng tính toán thử với Per nhé!

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~n~, ~q~ — tổng số nút và số lượng truy vấn.
• Dòng tiếp theo chứa ~n~ số nguyên ~v_i~ — giá trị của từng nút.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u_i~, ~v_i~ — mô tả một con đường.
• ~q~ dòng tiếp theo, mỗi dòng có một trong hai dạng:
  • ~1~ ~k~ ~x~ — đổi giá trị nút ~k~ thành ~x~;
  • ~2~ ~i~ ~j~ — hỏi độ vui vẻ của đường đi từ ~i~ tới ~j~.

Kết quả

Với mỗi truy vấn loại ~2~, in ra đáp án trên một dòng.

Ví dụ

Đầu vào:

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

Đầu ra:

21
20
4
20

Giải thích:

• Truy vấn ~1~: độ vui vẻ trên đường đi từ ~1~ tới ~5~ là ~1 \oplus 4 \oplus 16 = 21~.
• Sau truy vấn ~2~: ~v_1 = 16~.
• Truy vấn ~3~: đường đi từ ~3~ tới ~5~ có ~4 \oplus 16 = 20~.
• Truy vấn ~4~: đường đi từ ~1~ tới ~5~ có ~16 \oplus 4 \oplus 16 = 4~.
• Truy vấn ~5~: đường đi từ ~1~ tới ~3~ có ~16 \oplus 4 = 20~.

Giới hạn

• ~1 \le n, q \le 2 \cdot 10^5~
• ~0 \le v_i \le 10^9~
• ~1 \le u_i, v_i \le n~
• Truy vấn loại 1: ~1 \le k \le n~, ~0 \le x \le 10^9~
• Truy vấn loại 2: ~1 \le i, j \le n~