“要不我们挖出一道关于序列的旧题，然后让他们在树上做？”

—— 题目作者

题目描述

给定一棵树（无向无环图），其中每条边都有一定的长度。在这棵树的每个节点上都有一颗具有一定爆炸半径的地雷。如果某颗地雷爆炸，那么所有距离该地雷不超过其爆炸半径的节点上的地雷也会爆炸。两个节点之间的距离定义为它们之间简单路径上的边长之和。请确定，对于每颗地雷，如果我们“手动”引爆它，总共会有多少颗地雷爆炸。请注意，对于每颗地雷，我们独立地考虑其手动引爆，不受其他地雷手动引爆的影响。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示树的节点数（同时也是地雷的数量）。树的节点用 $1$ 到 $n$ 的整数编号。

第二行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$ ($0 \le r_i \le 10^{18}$)，其中 $r_i$ 表示位于第 $i$ 个节点上的地雷的爆炸半径。

接下来的 $n-1$ 行，每行包含三个整数 $a_i, b_i$ 和 $c_i$ ($1 \le a_i, b_i \le n; 1 \le c_i \le 10^{12}$)，表示节点 $a_i$ 和 $b_i$ 之间存在一条长度为 $c_i$ 的边。

保证输入包含一棵合法的树。

输出格式

输出仅一行，包含 $n$ 个整数，其中第 $i$ 个数应等于如果我们手动引爆位于树的第 $i$ 个节点上的地雷时，将会爆炸的地雷总数。

样例

输入

5
8 1 0 4 6
2 4 2
3 1 9
2 5 5
2 1 2

输出

4 1 1 4 2

说明

当我们手动引爆位于第四个节点的地雷时，它的爆炸将导致位于第一和第二个节点的地雷被引爆，随后位于第一个节点的地雷将导致位于第五个节点的地雷爆炸。因此，总共有四颗地雷爆炸。