You are given a tree with vertices. A tree is a connected undirected graph without cycles.
The tree has exactly one special vertex . Each vertex has an integer number written on it. Let's denote a function as the XOR of all values written on the vertices on the simple path connecting vertex and the special vertex . Let's denote another function $F(X)$
as the sum of all $G(i)$
where $X$
is the special vertex of the tree. More formally,
, where is the special vertex.
For each vertex , you have to print the value of treating vertex as the special vertex of the tree.
The simple path is the path that visits each vertex at most once. To know about XOR, you can read this.
The first line of the input will contain an integer (
)
, the number of the test cases.
In each of the test cases, the first line will contain an integer (
)
, the number of vertices of the tree. The next line will contain space-separated integers ,
,...,
(
)
, where the value written on vertex . Each of the next lines will contain two integers and denoting there is an undirected edge between vertex and vertex (
)
. It is guaranteed that the given edges form a tree.
The sum of over all the test cases will not be greater than .
For each test case, print space-separated integers , , …, in a line, where is the function described in the statement.
Input | Output |
---|---|
2 3 10 23 17 1 2 2 3 4 13 56 9 35 2 4 2 3 1 2 | 51 58 35 148 185 136 102 |
Notes: For test case , the tree will be like this: The value of each vertex is written in blue. Let's see what happens when vertex is the special vertex in this tree. So, |