markdown

E. Vasya 与一棵树

Vasya 有一棵包含 $n$ 个顶点的树，根节点为 $1$。初始时，所有顶点上的值均为 $0$。

记 $(i, j)$ 为顶点 $i$ 与 $j$ 之间的距离，即从 $i$ 到 $j$ 的最短路径上的边数。
另外，定义顶点 $v$ 的 $k$-子树 为满足以下两个条件的顶点集合 $x$：

• $v$ 是 $x$ 的祖先（每个顶点都是它自己的祖先）；
• $(x, v) \le k$。

Vasya 需要你处理 $m$ 个查询。第 $i$ 个查询是一个三元组 $v_i, d_i, x_i$。
对于每个查询，Vasya 将值 $x_i$ 加到 $v_i$ 的 $d_i$-子树中的每一个顶点上。

请在所有查询处理完毕后，输出树中每个顶点上的最终值。

输入

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）—— 树中顶点的数量。

接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$）—— 表示顶点 $x$ 与 $y$ 之间的一条边。保证给定的图是一棵树。

下一行包含一个整数 $m$（$1 \le m \le 3 \cdot 10^5$）—— 查询的数量。

接下来的 $m$ 行，每行包含三个整数 $v_i, d_i, x_i$（$1 \le v_i \le n$，$0 \le d_i \le 10^9$，$0 \le x_i \le 10^9$）—— 第 $i$ 个查询的描述。

输出

输出 $n$ 个整数。第 $i$ 个整数表示处理完所有查询后，顶点 $i$ 上的值。

样例

输入样例 1

5
1 2
1 3
2 4
2 5
3
1 1 1
2 0 10
4 10 100

输出样例 1

1 11 1 100 0

输入样例 2

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

输出样例 2

10 24 14 11 11

注释

在第一个样例中，初始时各顶点的值均为 $0, 0, 0, 0, 0$。
第一次查询后，各顶点的值变为 $1, 1, 1, 0, 0$。
第二次查询后，各顶点的值变为 $1, 11, 1, 0, 0$。
第三次查询后，各顶点的值变为 $1, 11, 1, 100, 0$。