Bạn được 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 đó ta thực hiện thao tác \(\oplus\) với tất cả các giá trị của 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\) (\(1 \le u,v \le n, 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}\) (\(1 \le u,v \le n\)).

Yêu cầu: Với mỗi truy vấn loại \(2\), in ra kết quả của số \(S\) trên một dòng.

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

Input

• Dòng thứ nhất chứa một số nguyên dương \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa một số nguyên dương \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ ba chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(0 \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.

Output

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

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n,q \le 1000\).
• Subtask \(2\) (\(10\%\) số điểm): cây thoả mãn điều kiện với hai cạnh \((u,v)\) bất kì \((u < v)\) thì \(u = \lfloor \frac{v}{2} \rfloor\).
• Subtask \(3\) (\(15\%\) số điểm): mọi truy vấn update (truy vấn loại 1) đều có \(u = v\).
• Subtask \(4\) (\(20\%\) số điểm): cây thoả mãn điều kiện đỉnh \(u\) được nối với đỉnh \(u+1\) với mọi \(1 \le u \le n-1\).
• Subtask \(5\) (\(20\%\) số điểm): cây thoả mãn điều kiện mỗi đỉnh không có nhiều hơn \(2\) cạnh.
• Subtask \(6\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

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

5