Life is like a game of chess; once a move is made, there is no turning back. Only by thinking through every step can one sail far.

Given a tree with $n$ nodes, node $i$ has $b_i$ chess pieces and can hold at most $a_i$ pieces. Now, consider a node $k$ as the root. In each operation, you can choose a node and move one of its pieces to its parent, provided that the number of pieces at the parent does not exceed its limit $a_i$. The goal is to minimize the sum of distances of all pieces to $k$.

Find the answer for each $k = 1, 2, \cdots, n$.

Input

The first line contains a positive integer $n$, representing the number of nodes in the tree.

The second line contains $n$ positive integers, where the $i$-th integer represents the maximum capacity $a_i$ of node $i$.

The third line contains $n$ positive integers, where the $i$-th integer represents the initial number of pieces $b_i$ at node $i$.

The next $n-1$ lines each contain two integers $u, v$, representing an edge in the tree.

Output

A single line containing $n$ integers, where the $i$-th integer is the answer when $i$ is the root.

Examples

Input 1

3
6 2 10 
6 0 2 
1 2
2 3

Output 1

2 6 0

Input 2

5
7 6 2 1 10 
3 5 0 0 7 
1 2
2 3
1 4
4 5

Output 2

10 12 20 14 9

Input 3

See $\texttt{chess/chess3.in}$ and $\texttt{chess/chess3.ans}$ in the contestant directory.

Constraints

For all data, $1 \le n \le 5 \times 10^5$, $0 \le b_i \le a_i$, $1 \le a_i \le 10^7$. The range of $a_i$ is kept small to avoid overflow of long long.

Subtask 1 (1 point): $b_i = 0$.

Subtask 2 (5 points): $n \le 2000$.

Subtask 3 (11 points): $n \le 8000$.

Subtask 4 (3 points): The tree is a chain, where for all $i \in [1, n-1] \cap \mathbb{Z}$, there is an edge between $i$ and $i+1$.

Subtask 5 (3 points): The tree is a star graph, where for all $i \in [2, n] \cap \mathbb{Z}$, there is an edge between $1$ and $i$.

Subtask 6 (6 points): The tree is generated randomly.

Subtask 7 (16 points): $a_i \le 5$.

Subtask 8 (22 points): $n \le 5 \times 10^4$.

Subtask 9 (16 points): $n \le 10^5$.

Subtask 10 (11 points): $n \le 2 \times 10^5$.

Subtask 11 (5 points): $n \le 3 \times 10^5$.

Subtask 12 (1 point): No additional constraints.

The random tree generation method is as follows: for each node $i \in [2, n]$, choose a node $p$ uniformly at random from $[1, i-1]$ and add an edge between $i$ and $p$.