给定一棵 $n$ 个顶点的树，其中第 $i$（$1 \le i \le n-1$）条边连接了顶点 $u_i$ 与 $v_i$（$1 \le u_i, v_i \le n$），其长度为 $w_i$。

在每个顶点上均埋藏着一棵地雷。第 $i$（$1 \le i \le n$）个顶点上的地雷的爆炸半径为 $R_i$ ，伤害值为 $h_i$ 。

我们定义 $\mathrm{dist}(i, j)$ 表示在树上顶点 $i$ 与顶点 $j$ 的最短距离。即，$\mathrm{dist}(i, j)$ 为顶点 $i$ 与 $j$ 之间唯一的简单路径的边权之和。

当顶点 $i$ 处的地雷爆炸时，所有距离其不超过 $R_i$ 的地雷都会一起爆炸。即，对于所有满足 $\mathrm{dist}(i, j) \le R_i$ 的地雷 $j$，如果其还没有爆炸，那么他也会被引爆。

对于每个 $i$（$i = 1, 2, \cdots, n$），你希望求出，如果在起始时引爆了顶点 $i$ 处的地雷，则最终所有被引爆的地雷的伤害值之和。

输入格式

输入的第一行包含一个整数 $n$。

接下来一行，包含 $n$ 个整数 $h_1, h_2, \cdots, h_n$，描述每个顶点上地雷的伤害值。

接下来一行，包含 $n$ 个整数 $R_1, R_2, \cdots, R_n$，描述每个顶点上地雷的半径。

接下来 $n-1$ 行，每行三个整数 $u_i, v_i, w_i$，描述一条边。

输出格式

输出一行，包含 $n$ 个整数。其中第 $i$（$i = 1, 2, \cdots, n$）个整数描述了如果在起始时引爆了顶点 $i$ 处的地雷，则最终所有被引爆的地雷的伤害值之和。

样例数据

样例 1 输入

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

样例 1 输出

10111 10010 10111 1000 10010

样例 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

样例 2 输出

19 19 4 1 5 9 8 8 5

子任务

对于所有数据，$1 \le n \le 10^5$，$1\le h_i\le 10^9$，$0 \le R_i \le 10^{18}$，$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^{12}$。