Vasya has a tree consisting of $n$ vertices with root in vertex $1$. At first all vertices has $0$ written on it.

Let $d(i, j)$ be the distance between vertices $i$ and $j$, i.e. number of edges in the shortest path from $i$ to $j$. Also, let's denote $k$-subtree of vertex $x$ — set of vertices $y$ such that next two conditions are met:

• $x$ is the ancestor of $y$ (each vertex is the ancestor of itself);
• $d(x, y) \le k$.

Vasya needs you to process $m$ queries. The $i$-th query is a triple $v_i$, $d_i$ and $x_i$. For each query Vasya adds value $x_i$ to each vertex from $d_i$-subtree of $v_i$.

Report to Vasya all values, written on vertices of the tree after processing all queries.

Input

The first line contains single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — number of vertices in the tree.

Each of next $n - 1$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$) — edge between vertices $x$ and $y$. It is guarantied that given graph is a tree.

Next line contains single integer $m$ ($1 \le m \le 3 \cdot 10^5$) — number of queries.

Each of next $m$ lines contains three integers $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$) — description of the $i$-th query.

Output

Print $n$ integers. The $i$-th integers is the value, written in the $i$-th vertex after processing all queries.

见题面 Input 部分

见题面 Output 部分

In the first exapmle initial values in vertices are $0, 0, 0, 0, 0$. After the first query values will be equal to $1, 1, 1, 0, 0$. After the second query values will be equal to $1, 11, 1, 0, 0$. After the third query values will be equal to $1, 11, 1, 100, 0$.