Description

Vasya有一棵树，它有n个节点，1号节点为根节点，初始所有点的权值为0。

定义以下两个东西：

1 函数d(i,j) 指节点i到j所经过边的数量。

2 x节点的k级子树，指满足以下条件点的集合：

① x为该点的祖先，规定自己也是自己的祖先。

②d(i,j)≤k。

Vasya有m条要求要你来解决：

给出v,d,x，将以v节点的d级子树的权值加上x。

当处理完Vasya所有的要求时，输出所有点的权值。

Format

Input

第1行包括一个整数，n，含义如上。

第2行到第n行，包括两个整数x和y，用空格隔开，表示两个点之间有一条边。

第n+1行有一个整数m，表示有m个要求。

第n+2行到第n+m+1行，有三个整数v,d,x，用空格隔开，含义如上。

1≤n≤3 * 1e5

1≤x,y≤n

1≤m≤3 * 1e5

1≤vi ≤n,0≤di ≤10^9,1≤xi ≤10^9

Output

共1行，包括n个数字，用空格隔开，第i个数字表示i号节点的权值。

Samples

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

1 11 1 100 0 

样例1解释：

在第一次修改后，修改了1,2,3号节点，他们的权值加1，所有的权值为1,1,1,0,0。

在第二次修改后，修改了2号节点，他的权值加10，所有的权值为1,11,1,0,0。

在第三次修改后，修改了4号节点，他的权值加100，所有的权值为1,11,1,100,0。