In Graph theory, tree is a simple connected acyclic graph. You are given a tree consists of N nodes numbered from 1 to N. Each node i have a value A_i associated with it. Your task is writing a program doing Q operations, each operations is 1 of 2 following types:

1. u, v: Assign A_u to v.
2. u, v: Calculate XOR sum of all value associated with nodes in unique single path from u to v.

Input

The first line is T - the number of test cases. Then T test cases follow.

Each test consists of several lines.

• The first line contains a single integer N - the number of nodes in tree.
• The second line contains N integers A₁, A₂, .., A_N where A_i is value associated with node i.
• Then N - 1 lines, each line contains two integer u and v (1 ≤ u, v ≤ N) denoting there is a direct edge between node u and node v. It is guaranteed that these edges form a tree.
• Then Q in a single line - the number of operations.
• Q lines follow, each line contains 3 integer t, u, v in which t is 1 or 2 denoting type of this operation described in the statement. If t = 1 then 1 ≤ u ≤ N, 1 ≤ v ≤ 10⁹. If t = 2 then 1 ≤ u, v ≤ N.

Output

For each operations of type 2, print the answer in a single line.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10⁵
• 1 ≤ A_i ≤ 10⁹
• 1 ≤ Q ≤ 10⁵