For a tree $T$ with root $r$, where each node $u$ has a value $a_u$ associated with it, the cost of the tree defined as:

$$\sum_{u\in T} (a_u \cdot d(r,u))$$

Here, this sum is taken over all nodes $u$ in the tree $T$, and $d(r,u)$ denotes the number of edges on the shortest path from node $r$ to node $u$ on a tree.

You are given a tree consisting of $n$ nodes, rooted at node $1$. Each node $i$ has a value $a_i$ assigned to it. For each $r$ from $1$ to $n$, please solve the following problem independently:

Consider the subtree of node $r$ with respect to node $1$. Formally, the subtree of node $r$ is the tree consisting of all nodes $u$ such that the shortest path from $1$ to $u$ contains $r$.

Find the maximum cost of the subtree after performing at most one operation of the following type on the subtree:

• Choose any node $u$ ($u \neq r$). Remove the edge from $u$ to the parent of node $u$$^{\text{∗}}$. Then, add an edge from $u$ to any node $v$ that is still reachable from $r$. It can be shown that after this operation, the graph remains a tree.

As an example, below shows an example of an operation with $r=1$,$u=5$, and $v=4$.

$^{\text{∗}}$Formally, remove the edge from $u$ to $p$, where $p$ is the unique node satisfying $d(u,p)=1$ and $d(u,r)=d(p,r)+1$

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the count of nodes in the tree.

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$).

Then $n − 1$ lines follow, the $i$-th line containing two integers $u$ and $v$ ($1 \le u, v \le n$) — the two nodes that the $i$-th edge connects.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ over all test cases.

Output

For each test case, print $n$ numbers – the answers for $r=1,2,\ldots,n$.

Note

In the first test case, for $r=1$, it is optimal to choose $u=5$ and $v=4$. The cost of the tree is then $1\cdot 0 + 3\cdot 1+2\cdot 2+1\cdot 3+2\cdot 4=18$. It can be shown that a larger cost cannot be obtained over all legal operations.

For $r=4$ for example, there is only $1$ node in the subtree, so there is no operation possible. The only possible cost of the subtree is $0$.