You are given a [tree] with N nodes rooted at node 1.
The i^{th} node of the tree has a value A_{i} assigned to it.

For the i^{th} node (1≤ i ≤ N), output the minimum value of [bitwise XOR] of the values of any two distinct nodes in the subtree of node i.

Formally, for each node i, find the value of $min(A_{x} \oplus A_{y})$, where $x \ne y$ and $x, y \in$ subtree of node i.
Note that since leaf nodes have only 1 node in their subtree, output -1 for all the leaf nodes.

------ Input Format ------

• First line will contain T, number of test cases. Then the test cases follow.
• Each test case begins with a single line of input, an integer N - the number of nodes in the tree.
• The following (N-1) lines each contain two integers, U and V, denoting an undirected edge between nodes U and V.
• The last line of each test case contains N integers. The i^{th} integer is the value assigned to i^{th} node.

It is assured that the edges given in the input form a tree.

------ Output Format ------

For each test case, output N integers where the i^{th} integer is the minimum value of [bitwise XOR] of the values of any two distinct nodes in the subtree of node i.
If node i is a leaf node, output -1 instead.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ U, V≤ N$ and $U\ne V$
$0 ≤ A_{i} ≤ 10^{15}$
- It is guaranteed that the edges given in the input form a tree.
- Sum of $N$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------
2
1
10
3
1 2
1 3
4 5 6
----- Sample Output 1 ------
-1
1 -1 -1

----- explanation 1 ------
Test case $1$: There is only one node in the tree which is a leaf node. Hence, the output is $-1$.

Test case $2$: The tree formed by the input of second test case is shown below:

• Nodes $2$ and Node $3$ are leaf nodes. Hence, the answer for them is $-1$.
• For the subtree formed by node $1$, the answer is $min((4\oplus5),(5\oplus6), (4\oplus6))$ which is $min(1, 3, 2) = 1$.

见题面

见题面