题目描述

一颗包含$\red{n}$个顶点的树，以$\red{1}$号顶点为根，最开始所有顶点的权值为$\red{0}$。

设$\red{d(i,j)}$为顶点$\red{i}$到顶点$\red{j}$的距离，我们定义顶点$\red{x}$的$\red{k-}$子树为满足以下条件的顶点$\red{y:}$

$\red{1}$、$\red{x}$是$\red{y}$的祖先（每个顶点是自己的祖先）；

$\red{2}$、$\red{d(x,y)<=k}$。

现在有$\red{m}$组操作，第$\red{i}$次操作包含$\red{u_i,d_i,x_i}$表示对$\red{u_i}$的$\red{d_i}$子树中所有顶点的权值加上$\red{x_i}$

计算$\red{m}$次操作后所有顶点的权值。

输入格式

第一行输入一个整数$\red{n，}$树的顶点数。

接下来$\red{n-1}$行，每行$\red{2}$个整数$\red{x,y,}$表示一条树边.保证给出的是一棵树。

接下来一行一个整数$\red{m，}$表示操作次数。

接下来$\red{m}$行，每行三个整数$\red{u_i,d_i,x_i}$

输出格式

一行，$\red{n}$个整数，表示$\red{m}$次操作后每个顶点的权值。

样例

输入样例

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

输出样例

1 11 1 100 0

提示

对于$\red{50\%}$的数据，$\red{1<=n,m<=10^3}$。

对于$\red{100\%}$的数据，$\red{1<=n,m<=3\times 10^5,1<=u_i<=n,0<=d_i<=10^9,1<=x_i<=10^9}$。