To defeat Accelerator, the Misaka Sisters are joining forces! They will station themselves by the wind turbines in Academy City to weaken Accelerator's ability.

Academy City has $n$ wind turbines, and there are exactly $n$ Misaka Sisters. The connection of the Misaka Network forms a tree. Each wind turbine has a power $w_i$. When Accelerator appears at the location of the $i$-th Misaka Sister, all Misakas will activate their abilities towards him. However, the Misakas' abilities can only be activated when they work together; every pair of Misakas combines to generate energy to resist Accelerator. If the location of Accelerator is considered the root, the energy generated by a pair of sisters $u < v$ is $w_{\mathrm{lca}(u, v)}$. The total energy generated by the Misaka Network is the sum of the energy generated by every pair of sisters. You are required to calculate the total energy generated by the Misaka Network for every possible location of Accelerator.

Input

The first line contains a single positive integer $n$, representing the number of wind turbines.

The next line contains $n$ positive integers, where the $i$-th integer $w_i$ represents the power of the $i$-th wind turbine.

The next $n - 1$ lines each contain two positive integers $u$ and $v$, where $1 \le u, v \le n$, representing an edge between $u$ and $v$.

Output

Output a single line containing $n$ integers, where the $i$-th integer represents the total energy generated by the Misakas if Accelerator is at location $i$.

Examples

Input 1

3
2 5 7
3 2
1 2

Output 1

9 15 19

Subtasks

For test cases 1-4: $n \le 50$

For test cases 5-8: $n \le 500$

For test cases 9-12: $n \le 2000$

For test cases 13-14: $n \le 5 \times 10^4$, the tree is a binary tree

For test cases 15-16: $n \le 5 \times 10^4$, the tree is a chain

For test cases 17-18: $n \le 5 \times 10^4$

For test cases 19-20: $n \le 5 \times 10^5$, the tree is a chain

For test cases 21-22: $n \le 5 \times 10^5$, the tree is a star graph

For test cases 23-25: $n \le 5 \times 10^5$

For $100\%$ of the data, it is guaranteed that $n \le 5 \times 10^5$ and $0 \le w_i \le 10^6$.