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 nhiều điểm vui chơi khác nhau dành cho bò (tàu lượn bò đặc biệt nổi tiếng).

Có tổng cộng \(N\) điểm vui chơi khác nhau (\(2 \leq N \leq 10^5\)). Một số cặp điểm vui chơi được nối với nhau bởi tổng cộng \(N-1\) con đường, sao cho giữa hai điểm vui chơi bất kỳ tồn tại duy nhất một lộ trình gồm các con đường này. Mỗi điểm vui chơi \(i\) có một giá trị thích thú nguyên \(e_i\). Giá trị này có thể thay đổi trong ngày, vì một số điểm hấp dẫn hơn vào buổi sáng còn những điểm khác hấp dẫn hơn vào cuối buổi chiều.

Một con bò đi từ điểm vui chơi \(i\) đến điểm vui chơi \(j\) sẽ được trải nghiệm tất cả các điểm trên lộ trình từ \(i\) đến \(j\). Điều kỳ lạ là tổng giá trị thích thú của toàn bộ lộ trình này được tính bằng phép XOR theo bit của tất cả các giá trị thích thú trên lộ trình, bao gồm cả giá trị của điểm \(i\) và điểm \(j\).

Hãy giúp những con bò xác định giá trị thích thú của các lộ trình mà chúng dự định sử dụng trong chuyến đi Cow Land tiếp theo.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và số lượng truy vấn \(Q\) (\(1 \leq Q \leq 10^5\)). Dòng tiếp theo chứa \(e_1 \ldots e_N\) (\(0 \leq e_i \leq 10^9\)). Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một con đường bằng hai mã số nguyên của các điểm vui chơi \(a\) và \(b\) (đều nằm trong phạm vi \(1 \ldots N\)). Cuối cùng, mỗi dòng trong \(Q\) dòng cuối mô tả một phép cập nhật một trong các giá trị \(e_i\) hoặc một truy vấn giá trị thích thú của một lộ trình. Dòng có dạng 1 \(i\) \(v\) cho biết cần cập nhật \(e_i\) thành giá trị \(v\), còn dòng có dạng 2 \(i\) \(j\) là truy vấn giá trị thích thú của lộ trình nối điểm vui chơi \(i\) và \(j\).

Phân nhóm

Trong các test có tổng điểm không quá 50% số điểm, giá trị của các điểm vui chơi sẽ không thay đổi.

Dữ liệu ra

Với mỗi truy vấn có dạng 2 \(i\) \(j\), in trên một dòng giá trị thích thú của lộ trình từ \(i\) đến \(j\).

Ví dụ

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

21
20
4
20

Nguồn

USACO 2019 February Contest, Gold — Cow Land

Tác giả: Charles Bailey.