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

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

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

Vasya needs you to process m m queries. The i i -th query is a triple v i  vi , d i  di and x i  xi . For each query Vasya adds value x i  xi to each vertex from d i  di -subtree of v i  vi .

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

Input

The first line contains single integer n n (1≤n≤3⋅10 5  1≤n≤3⋅105 ) — number of vertices in the tree.

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

Next line contains single integer m m (1≤m≤3⋅10 5  1≤m≤3⋅105 ) — number of queries.

Each of next m m lines contains three integers v i  vi , d i  di , x i  xi (1≤v i ≤n 1≤vi≤n , 0≤d i ≤10 9  0≤di≤109 , 1≤x i ≤10 9  1≤xi≤109 ) — description of the i i -th query.

Output

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

Examples

5

1 2

1 3

2 4

2 5

3

1 1 1

2 0 10

4 10 100

1 11 1 100 0

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

10 24 14 11 11

Note

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

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define ll long long

using namespace std;

const int maxn=;

int dep[maxn],N,Laxt[maxn],Next[maxn],To[maxn],cnt;

int laxt2[maxn],next2[maxn],D[maxn],X[maxn],tot; ll ans[maxn];

void add(int u,int v){

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;

}

void add2(int u,int d,int x){

    next2[++tot]=laxt2[u]; laxt2[u]=tot; D[tot]=d; X[tot]=x;

}

void dfs(int u,int f,ll sum,ll *mp)

{

    dep[u]=dep[f]+; sum-=mp[dep[u]];

    for(int i=laxt2[u];i;i=next2[i]){

        sum+=X[i];if(dep[u]+D[i]+<=N) mp[dep[u]+D[i]+]+=X[i];

    }

    ans[u]=sum;

    for(int i=Laxt[u];i;i=Next[i])

      if(To[i]!=f) dfs(To[i],u,sum,mp);

    for(int i=laxt2[u];i;i=next2[i]){

        sum-=X[i];if(dep[u]+D[i]+<=N) mp[dep[u]+D[i]+]-=X[i];

    }

}

ll mp[maxn];

int main()

{

    int u,v,x,Q; scanf("%d",&N);

    rep(i,,N-) {

        scanf("%d%d",&u,&v);

        add(u,v); add(v,u);

    }

    scanf("%d",&Q);

    rep(i,,Q) {

        scanf("%d%d%d",&u,&v,&x);

        add2(u,v,x);

    }

    dfs(,,0LL,mp);

    rep(i,,N) printf("%lld ",ans[i]);

    return ;

}