Cho một cây có \(n\) đỉnh và \(n-1\) cạnh và một mảng \(a\) gồm \(n\) phần tử. Ban đầu giá trị của đỉnh thứ \(i\) bằng \(a_i\)​. Có hai loại truy vấn:

• "1 u v p": Gọi \(s_1,s_2,...s_k\) là các đỉnh trên đường đi từ \(u\) đến \(v\). Sau đó thực hiện thao tác \(\oplus\) với tất cả các đỉnh đó, nói cách khác ta gán cho \(a_{s_1} = a_{s_1} \oplus p, a_{s_2} = a_{s_2} \oplus p, ..., a_{s_k} = a_{s_k} \oplus p\) \((0 \le p \le 2^{10}-1)\).
• "2 u v": Gọi \(s_1,s_2,...s_k\) là các đỉnh trên đường đi từ \(u\) đến \(v\). Sau đó cần đưa ra tổng trọng số đỉnh của các nút trên đường đi từ \(u\) đến \(v\), nói cách khác cần đưa ra tổng \(S=a_{s_1}+a_{s_2}...+a_{s_k}\)

Biểu thức \(x \oplus y\) biểu diễn phép toán tử \(XOR\) của hai số \(x\) và \(y\).

Yêu cầu

• Với mỗi truy vấn loại \(2\), đưa ra kết quả trên một dòng.

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên dương \(n\) \((1 \le n \le 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...a_n\) \((1 \le a_i \le 2^{10}-1)\)
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) - mô tả một cạnh của cây.
• Dòng tiếp theo chứa một số nguyên dương \(q\) \((q \le 10^5)\) - số lượng truy vấn.
• \(q\) dòng cuối cùng, mỗi dòng chứa một truy vấn như mô tả ở trên.

Dữ liệu ra

• Với mỗi truy vấn loại \(2\), đưa ra kết quả bài toán trên một dòng.

Input 1

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

Output 1

5