Vasya 有一个由 $$$n$$$ 个顶点组成的树,根位于顶点 $$$1$$$。首先,所有顶点上都写有$$$0$$$。
令 $$$d(i, j)$$$ 为顶点 $$$i$$$ 和 $$$j$$$ 之间的距离,即从 $$$i$$$ 到 $$$j$$$ 的最短路径中的边数。另外,让我们表示 $$$k$$$ - 顶点 $$$x$$$ 的子树 - 顶点集 $$$y$$$ ,以满足接下来的两个条件:
- $$$x$$$ 是 $$$y$$$ 的祖先(每个顶点都是其自身的祖先);
- $$$d(x, y) \le k$$$。
Vasya 需要您处理 $$$m$$$ 查询。第 $$$i$$$ 查询是三重 $$$v_i$$$、$$$d_i$$$ 和 $$$x_i$$$。对于每个查询,Vasya 将值 $$$x_i$$$ 添加到 $$$d_i$$$ 子树 $$$v_i$$$ 中的每个顶点。
向 Vasya 报告所有值,在处理所有查询后写入树的顶点。
输入
第一行包含单个整数 $$$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$$$, $$$1 \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$$$。