You are given a tree with n vertices labeled from 1 to n. An integer a_i is written on vertex i for i = 1, 2, …, n. You want to make all a_i equal by performing some (possibly, zero) spells.
Suppose you root the tree at some vertex. On each spell, you can select any vertex v and any non-negative integer c. Then for all vertices i in the subtree^ of v, replace a_i with a_i ⊕ c. The cost of this spell is s · c, where s is the number of vertices in the subtree. Here ⊕ denotes the bitwise XOR operation .
Let m_r be the minimum possible total cost required to make all a_i equal, if vertex r is chosen as the root of the tree. Find m_1, m_2, …, m_n.
^ Suppose vertex r is chosen as the root of the tree. Then vertex i belongs to the subtree of v if the simple path from i to r contains v.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^4). The description of the test cases follows.The first line of each test case contains a single integer n (1 ≤ n ≤ 2 · 10^5).The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i 2^20).Each of the next n-1 lines contains two integers u and v (1 ≤ u, v ≤ n), denoting that there is an edge connecting two vertices u and v.It is guaranteed that the given edges form a tree.It is guaranteed that the sum of n over all test cases does not exceed 2 · 10^5.
Output
For each test case, print m_1, m_2, …, m_n on a new line.
Examples
Note
In the first test case, to find m_1 we root the tree at vertex 1. In the first spell, choose v=2 and c=1. After performing the spell, a will become [3, 3, 0, 1]. The cost of this spell is 3. In the second spell, choose v=3 and c=3. After performing the spell, a will become [3, 3, 3, 1]. The cost of this spell is 3. In the third spell, choose v=4 and c=2. After performing the spell, a will become [3, 3, 3, 3]. The cost of this spell is 2. Now all the values in array a are equal, and the total cost is 3 + 3 + 2 = 8.The values m_2, m_3, m_4 can be found analogously.In the second test case, the goal is already achieved because there is only one vertex.