Given a tree with $n$ vertices, where the $i$-th edge ($1 \le i \le n-1$) connects vertices $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) with length $w_i$.

A mine is buried at each vertex. The mine at vertex $i$ ($1 \le i \le n$) has an explosion radius $R_i$ and a damage value $h_i$.

We define $\mathrm{dist}(i, j)$ as the shortest distance between vertex $i$ and vertex $j$ in the tree. That is, $\mathrm{dist}(i, j)$ is the sum of the weights of the edges on the unique simple path between vertices $i$ and $j$.

When the mine at vertex $i$ explodes, all mines within a distance of at most $R_i$ will explode as well. Specifically, for all mines $j$ such that $\mathrm{dist}(i, j) \le R_i$, if they have not yet exploded, they will be triggered.

For each $i$ ($i = 1, 2, \cdots, n$), you want to find the total damage value of all mines that eventually explode if you trigger the mine at vertex $i$ initially.

Input

The first line contains an integer $n$.

The next line contains $n$ integers $h_1, h_2, \cdots, h_n$, describing the damage value of the mine at each vertex.

The next line contains $n$ integers $R_1, R_2, \cdots, R_n$, describing the explosion radius of the mine at each vertex.

The next $n-1$ lines each contain three integers $u_i, v_i, w_i$, describing an edge.

Output

Output a single line containing $n$ integers. The $i$-th integer ($i = 1, 2, \cdots, n$) describes the total damage value of all mines that eventually explode if the mine at vertex $i$ is triggered initially.

Examples

Input 1

5
1 10 100 1000 10000
3 2 3 1 3
1 2 3
1 3 1
2 4 3
2 5 2

Output 1

10111 10010 10111 1000 10010

Input 2

9
3 1 4 1 5 9 2 6 5
9 9 8 2 4 4 3 5 3
1 2 9
1 3 10
1 4 5 
2 5 7
2 6 8
5 7 6
7 8 3
6 9 10

Output 2

19 19 4 1 5 9 8 8 5