Bài 3. Truy vấn trên cây (TREEQUERY)

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm \(n\) đỉnh và \(n-1\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\), đỉnh thứ \(i\) có trọng số là \(w_i\).

Ví dụ, ta có một cây với gốc là 1:

• Cây gốc 1 bao gồm các đỉnh \(\{1,2,3,4,5,6,7\}\).
• Cây con có gốc là 2 bao gồm các đỉnh \(\{2,6,5,4\}\).
• Cây con có gốc là 3 bao gồm các đỉnh \(\{3,7\}\).

Ta định nghĩa \(S(\mathrm{root},a)\) là tổng trọng số của các đỉnh trong cây con có gốc \(a\), khi cây được định nghĩa với gốc là \(\mathrm{root}\), tức là:

Bạn hãy trả lời \(q\) truy vấn, mỗi truy vấn thuộc một trong hai dạng sau:

1. Truy vấn loại 1: 1 a b — Ghi ra giá trị \(S(a,b)\).
2. Truy vấn loại 2: 2 a b v — Chọn gốc của cây là \(a\), và cập nhật trọng số của các đỉnh \(u\) thuộc cây con có gốc \(b\) theo phép XOR với \(v\), tức là:

với \(\oplus\) là phép bitwise XOR trong C++.

Input

Cho trong file TREEQUERY.INP, có cấu trúc:

• Dòng 1: Chứa số nguyên \(n\), là số đỉnh của cây \((1 \le n \le 10^5)\).
• Dòng 2: Chứa \(n\) số nguyên \(w_1,w_2,\ldots,w_n\), là trọng số các đỉnh \((0 \le w_i \le 10^9)\).
• Trên \(n-1\) dòng tiếp theo: Mỗi dòng chứa hai số nguyên \(u,v\) biểu diễn một cạnh giữa đỉnh \(u\) và đỉnh \(v\) của cây \((1 \le u,v \le n)\).
• Dòng tiếp theo chứa số nguyên \(q\), là số truy vấn \((1 \le q \le 10^5)\).
• Trên \(q\) dòng tiếp theo, mỗi dòng biểu diễn một truy vấn:
• Truy vấn loại 1: 1 a b \((1 \le a,b \le n)\) — Ghi ra \(S(a,b)\).
• Truy vấn loại 2: 2 a b v \((1 \le a,b \le n,\ 1 \le v \le 10^9)\) — Cập nhật trọng số các đỉnh trong cây con gốc \(b\) khi cây có gốc \(a\), theo phép XOR với \(v\).

Output

Ghi ra file TREEQUERY.OUT:

• Với mỗi truy vấn loại 1, ghi ra một dòng là kết quả \(S(a,b)\).

Example

7
1 2 3 4 5 6 7
1 2
1 3
2 4
2 6
3 7
6 5
3
1 1 2
2 1 2 1
1 1 2

17
19

Chú ý: Thời gian thực hiện chương trình tối đa cho mỗi bộ test bất kỳ là không quá 01 giây.

Scoring

• 20% số test tương ứng với 20% số điểm của bài có \(n,q \le 2000\).
• 20% số test tương ứng với 20% số điểm của bài không có truy vấn loại 2.
• 20% số test tương ứng với 20% số điểm ứng với trường hợp mỗi đỉnh trên cây có tối đa hai đỉnh kề với nó.
• 20% số test tương ứng với 20% số điểm của bài không có \(a=1\).
• 20% số test còn lại tương ứng với 20% số điểm của bài không có ràng buộc gì thêm.