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) ≤ 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 ≤ n ≤ 3 ⋅ 10^5) — number of vertices in the tree.

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

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

Each of next m lines contains three integers v_i, d_i, x_i (1 ≤ v_i ≤ n, 0 ≤ d_i ≤ 10^9, 1 ≤ x_i ≤ 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.

Examples

Input


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


Output


1 11 1 100 0 


Input


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


Output


10 24 14 11 11 

Note

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.
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using std::nth_element;
template <class type>
inline const type min(const type &a, const type &b) {
  return a < b ? a : b;
}
template <class type>
inline const type max(const type &a, const type &b) {
  return a > b ? a : b;
}
template <class type>
inline const void read(type &in) {
  in = 0;
  char ch = getchar();
  bool f = 0;
  while (ch < 48 || ch > 57) {
    if (ch == '-') f = 1;
    ch = getchar();
  }
  while (ch > 47 && ch < 58)
    in = (in << 3) + (in << 1) + (ch & 15), ch = getchar();
  if (f) in = -in;
}
const int N = 3e5 + 10, K = 2, inf = 2147483647;
long long ans[N];
int n, m, head[N], edc, next[N << 1], to[N << 1], dfn[N], end[N], dep[N],
    dot[N];
inline const void link(int u, int v) {
  next[++edc] = head[u];
  to[head[u] = edc] = v;
  next[++edc] = head[v];
  to[head[v] = edc] = u;
}
inline const void dfs(int p, int fa) {
  dot[dfn[p] = ++*dfn] = p;
  for (int son, i = head[p]; i; i = next[i])
    if ((son = to[i]) ^ fa) dep[son] = dep[p] + 1, dfs(son, p);
  end[p] = *dfn;
}
int f;
struct point {
  int d[K];
  long long w;
  inline point() {}
  inline point(const int &x, const int &y, const int &w = 0) : w(w) {
    d[0] = x;
    d[1] = y;
  }
  inline const bool operator<(const point &p) const { return d[f] < p.d[f]; }
} a[N];
template <const int k, const int maxn>
class KD_Tree {
 private:
  struct tree {
    long long add;
    tree *son[2];
    point range, mn, mx;
    inline const void pushup() {
      for (int i = 0; i < k; i++)
        mn.d[i] = min(range.d[i], min(son[0]->mn.d[i], son[1]->mn.d[i])),
        mx.d[i] = max(range.d[i], max(son[0]->mx.d[i], son[1]->mx.d[i]));
    }
    inline const bool out(const point &lower, const point &upper) {
      for (int i = 0; i < k; i++)
        if (mn.d[i] > upper.d[i] || mx.d[i] < lower.d[i]) return 1;
      return 0;
    }
    inline const bool in(const point &lower, const point &upper) {
      for (int i = 0; i < k; i++)
        if (!(mn.d[i] >= lower.d[i] && mx.d[i] <= upper.d[i])) return 0;
      return 1;
    }
    inline const bool at(const point &lower, const point &upper) {
      for (int i = 0; i < k; i++)
        if (!(range.d[i] >= lower.d[i] && range.d[i] <= upper.d[i])) return 0;
      return 1;
    }
  } * root, memory_pool[maxn], *null, *tail;
  inline const void init() {
    tail = memory_pool;
    null = tail++;
    null->son[0] = null->son[1] = null;
    for (int i = 0; i < k; i++) null->mn.d[i] = inf, null->mx.d[i] = -inf;
  }
  inline tree *spawn(const point &x) {
    tree *p = tail++;
    p->range = p->mn = p->mx = x;
    p->son[0] = p->son[1] = null;
    return p;
  }
  inline tree *build(int l, int r, int d) {
    if (l > r) return null;
    const int mid = l + r >> 1;
    f = d;
    nth_element(a + l, a + mid, a + r + 1);
    tree *p = spawn(a[mid]);
    if (l == r) return p;
    p->son[0] = build(l, mid - 1, (d + 1) % k);
    p->son[1] = build(mid + 1, r, (d + 1) % k);
    p->pushup();
    return p;
  }
  inline const void add(tree *p, const point &x, const point &y, const int &w) {
    if (p == null) return;
    if (p->out(x, y)) return;
    if (p->in(x, y)) return p->add += w, void();
    if (p->at(x, y)) p->range.w += w;
    add(p->son[0], x, y, w);
    add(p->son[1], x, y, w);
  }
  inline const void check(tree *p, long long add) {
    if (p == null) return;
    ans[dot[p->range.d[0]]] = p->range.w + (add += p->add);
    check(p->son[0], add);
    check(p->son[1], add);
  }

 public:
  inline const void build() {
    init();
    root = build(1, n, 0);
  }
  inline const void add(int x1, int y1, int x2, int y2, int w) {
    add(root, point(x1, y1), point(x2, y2), w);
  }
  inline const void check() { check(root, 0); }
};
KD_Tree<K, N> kdt;
int main() {
  read(n);
  for (int u, v, i = 1; i < n; i++) read(u), read(v), link(u, v);
  dfs(1, 0);
  for (int i = 1; i <= n; i++) a[i] = point(dfn[i], dep[i]);
  kdt.build();
  read(m);
  for (int u, k, w; m--;)
    read(u), read(k), read(w), kdt.add(dfn[u], dep[u], end[u], k + dep[u], w);
  kdt.check();
  for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
  putchar('\n');
  return 0;
}
