You are given an undirected tree with $N$ nodes rooted at node 1. Every node has a value $A[i]$ assigned to it. You are required to answer $Q$ queries of the following type:

• $U V X$
  • Select a subtree with $U$ as the root node and subtree with $V$ as the root node and swap their positions. That is, detach both the subtrees and swap their positions.
  • If node $U$ is an ancestor of node $V$ or node $V$ is an ancestor of node $U$, the above Swap operation is not performed.
  • Find the sum of node values present in the subtree rooted at node $X$.
  • If the Swap operation is performed, then redo this operation. That is, swap the subtree with $U$ as the root node and subtree with $V$ as the root node.

Determine the required answer for $Q$ queries.

Note

• Assume 1-based indexing.
• A node $u$ is said to be an ancestor of node $v$ if node $u$ lies on a simple path between the root and node $v$.
• Here, Redo means re-doing the operation performed.

Input format

• The first line contains a single integer $T$ that denotes the number of test cases.
• For each test case:
  • The first line contains an integer $N$.
  • The second line contains $N$ space-separated integers denoting array $A$.
  • The next $N - 1$ line contains two space-separated integers $u v$ denoting an edge between node $u$ and $v$.
  • The next line contains an integer $Q$.
  • The next $Q$ lines contain three space-separated integers $U V X$ denoting the query.

Output format

For each test case, print $Q$ space-separated integers denoting the sum of node values present in the subtree rooted at node $X$ after the swap operation is performed. Print the output for each test case in a new line.

Constraints

$1 \le T \le 10 \\ 1 \le N, Q \le 10^5 \\ 1 \le A[i] \le 10^9 \\ 1 \le U, V, X \le N$