In the year 3000, the Earth Alliance has conquered $N$ planets in the galaxy. Due to budget considerations, the government has established only $N-1$ bidirectional space-time tunnels between the planets, ensuring that any two planets are mutually reachable. For administrative reasons, the governor of the $i$-th planet requires that no citizen may use space-time tunnels to leave that planet more than $H_i$ times in a year (this statistic is based on the number of departures; if you have already used a tunnel to leave the planet $H_i$ times, you cannot use a space-time tunnel to leave that planet again for the rest of the year). Louis Paosen is an interstellar traveler who wishes to use as many space-time tunnels as possible, but he does not want the planet where he eventually settles to have overly harsh conditions. Therefore, he wants to know, for each planet $i$, the maximum number of space-time tunnels he can use during an interstellar journey that starts at planet $0$ and ends at planet $i$.

Input

The first line contains an integer $N$. The next line contains $N$ integers $H_i$, representing the departure limit for each planet. The following $N-1$ lines each contain two integers, representing a space-time tunnel connection between two planets. The planets are numbered starting from $0$, and Louis Paosen starts at planet $0$.

Output

The output contains $N$ lines, each containing an integer representing the maximum number of space-time tunnels that can be used if the journey ends at that planet.

Constraints

• $40\%$ of the data: $N \le 500$
• $100\%$ of the data: $N \le 50000$
• The departure limits for all planets satisfy $1 \le H_i \le 40000$, and for each planet, $H_i$ is greater than or equal to the number of planets directly connected to it (i.e., its degree).

Examples

Input 1

3
2 6 2
0 1
1 2

Output 1

8
7
8