#include <bits/stdc++.h>
using namespace std;
const int INFL = (int)1e9;
const long long int INFLL = (long long int)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
bool nearlyeq(double x, double y) { return abs(x - y) < 1e-9; }
bool inrange(int x, int t) { return x >= 0 && x < t; }
long long int rndf(double x) {
  return (long long int)(x + (x >= 0 ? 0.5 : -0.5));
}
long long int floorsqrt(double x) {
  long long int m = (long long int)sqrt(x);
  return m + (m * m <= (long long int)(x) ? 0 : -1);
}
long long int ceilsqrt(double x) {
  long long int m = (long long int)sqrt(x);
  return m + ((long long int)x <= m * m ? 0 : 1);
}
long long int rnddiv(long long int a, long long int b) {
  return (a / b + (a % b * 2 >= b ? 1 : 0));
}
long long int ceildiv(long long int a, long long int b) {
  return (a / b + (a % b == 0 ? 0 : 1));
}
long long int gcd(long long int m, long long int n) {
  if (n == 0)
    return m;
  else
    return gcd(n, m % n);
}
class Binary_Indexed_Tree {
 private:
  vector<long long int> bits;
  int n;

 public:
  Binary_Indexed_Tree(vector<long long int> a) {
    n = a.size();
    bits = vector<long long int>(n, 0);
    for (int i = 0; i < (int)a.size(); i++) add(i, a[i]);
  }
  void add(int k, long long int x) {
    ++k;
    for (int index = k; index <= n; index += index & -index) {
      bits[index - 1] += x;
    }
  }
  long long int sum(int s, int t) {
    long long int ret = 0;
    for (int index = t; index > 0; index -= index & -index) {
      ret += bits[index - 1];
    }
    for (int index = s; index > 0; index -= index & -index) {
      ret -= bits[index - 1];
    }
    return ret;
  }
};
struct tree_t {
  int n;
  vector<pair<int, int>> edges;
  vector<vector<pair<int, long long int>>> vals;
  vector<long long int> costs;
};
class Tree {
 private:
  struct node {
    int id;
    vector<int> childs;
    int parent = -1;
    int deg = -1;
    int eid = -1;
    int subtree_n = 1;
    vector<pair<int, long long int>> val;
    long long int cost;
    bool operator<(const node &another) const {
      return deg != another.deg ? deg < another.deg : id < another.id;
    }
  };
  struct edgeinfo {
    int eid;
    int to;
    long long int cost;
  };
  int n;
  static const long long int init_cost = 1;
  vector<vector<edgeinfo>> edges;
  void tree_construction() {
    leaves = {};
    queue<int> que;
    que.push(root);
    while (que.size()) {
      int a = que.front();
      que.pop();
      deg_order.push_back(a);
      if (a == Tree::root) nodes[a].deg = 0;
      int leaf_flag = true;
      for (int i = 0; i < (int)edges[a].size(); i++) {
        int b = edges[a][i].to;
        if (nodes[b].deg != -1) {
          nodes[a].parent = b;
          nodes[a].eid = edges[a][i].eid;
          nodes[a].cost = edges[a][i].cost;
          nodes[a].deg = nodes[b].deg + 1;
        } else {
          leaf_flag = false;
          nodes[a].childs.push_back(b);
          que.push(b);
        }
      }
      if (leaf_flag) leaves.push_back(a);
    }
    for (int i = (int)n - 1; i >= 0; i--) {
      int a = deg_order[i];
      for (int j = 0; j < (int)nodes[a].childs.size(); j++) {
        int b = nodes[a].childs[j];
        nodes[a].subtree_n += nodes[b].subtree_n;
      }
    }
  }

 public:
  vector<node> nodes;
  vector<int> deg_order;
  vector<int> leaves;
  int root;
  Tree(tree_t T, int root) {
    n = T.n;
    nodes.resize(n);
    for (int i = 0; i < (int)n; i++) {
      nodes[i].id = i;
      nodes[i].val = T.vals[i];
      nodes[i].cost = init_cost;
    }
    edges.resize(n);
    for (int i = 0; i < (int)n - 1; i++) {
      edges[T.edges[i].first].push_back(
          {i, T.edges[i].second,
           ((int)(T.costs.size()) > i ? T.costs[i] : init_cost)});
      edges[T.edges[i].second].push_back(
          {i, T.edges[i].first,
           ((int)(T.costs.size()) > i ? T.costs[i] : init_cost)});
    }
    Tree::root = root;
    tree_construction();
    return;
  }
  vector<long long int> ans;
  Binary_Indexed_Tree *bit;
  void dfs(int id) {
    for (auto fac : nodes[id].val) {
      bit->add(nodes[id].deg + fac.first, fac.second);
    }
    ans[id] = bit->sum(nodes[id].deg, n * 2 + 8);
    for (auto a : nodes[id].childs) {
      dfs(a);
    }
    for (auto fac : nodes[id].val) {
      bit->add(nodes[id].deg + fac.first, -fac.second);
    }
  }
  void solve() {
    ans.resize(n);
    bit = new Binary_Indexed_Tree(vector<long long int>(n * 2 + 10, 0));
    dfs(0);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ;
  tree_t T;
  cin >> T.n;
  for (int i = 0; i < (int)T.n - 1; i++) {
    int s, t;
    cin >> s >> t;
    s--;
    t--;
    T.edges.push_back({s, t});
  }
  T.vals.resize(T.n);
  int q;
  cin >> q;
  for (int i = 0; i < (int)q; i++) {
    int v, d;
    cin >> v >> d;
    v--;
    d = min(d, T.n + 3);
    long long int x;
    cin >> x;
    T.vals[v].push_back({d, x});
  }
  Tree tree(T, 0);
  tree.solve();
  for (int extra_i = 0; extra_i < (int)tree.ans.size(); extra_i++) {
    cout << tree.ans[extra_i] << " ";
  }
  cout << endl;
  ;
}

### Prompt

Create a solution in Cpp for the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INFL = (int)1e9;
const long long int INFLL = (long long int)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
bool nearlyeq(double x, double y) { return abs(x - y) < 1e-9; }
bool inrange(int x, int t) { return x >= 0 && x < t; }
long long int rndf(double x) {
  return (long long int)(x + (x >= 0 ? 0.5 : -0.5));
}
long long int floorsqrt(double x) {
  long long int m = (long long int)sqrt(x);
  return m + (m * m <= (long long int)(x) ? 0 : -1);
}
long long int ceilsqrt(double x) {
  long long int m = (long long int)sqrt(x);
  return m + ((long long int)x <= m * m ? 0 : 1);
}
long long int rnddiv(long long int a, long long int b) {
  return (a / b + (a % b * 2 >= b ? 1 : 0));
}
long long int ceildiv(long long int a, long long int b) {
  return (a / b + (a % b == 0 ? 0 : 1));
}
long long int gcd(long long int m, long long int n) {
  if (n == 0)
    return m;
  else
    return gcd(n, m % n);
}
class Binary_Indexed_Tree {
 private:
  vector<long long int> bits;
  int n;

 public:
  Binary_Indexed_Tree(vector<long long int> a) {
    n = a.size();
    bits = vector<long long int>(n, 0);
    for (int i = 0; i < (int)a.size(); i++) add(i, a[i]);
  }
  void add(int k, long long int x) {
    ++k;
    for (int index = k; index <= n; index += index & -index) {
      bits[index - 1] += x;
    }
  }
  long long int sum(int s, int t) {
    long long int ret = 0;
    for (int index = t; index > 0; index -= index & -index) {
      ret += bits[index - 1];
    }
    for (int index = s; index > 0; index -= index & -index) {
      ret -= bits[index - 1];
    }
    return ret;
  }
};
struct tree_t {
  int n;
  vector<pair<int, int>> edges;
  vector<vector<pair<int, long long int>>> vals;
  vector<long long int> costs;
};
class Tree {
 private:
  struct node {
    int id;
    vector<int> childs;
    int parent = -1;
    int deg = -1;
    int eid = -1;
    int subtree_n = 1;
    vector<pair<int, long long int>> val;
    long long int cost;
    bool operator<(const node &another) const {
      return deg != another.deg ? deg < another.deg : id < another.id;
    }
  };
  struct edgeinfo {
    int eid;
    int to;
    long long int cost;
  };
  int n;
  static const long long int init_cost = 1;
  vector<vector<edgeinfo>> edges;
  void tree_construction() {
    leaves = {};
    queue<int> que;
    que.push(root);
    while (que.size()) {
      int a = que.front();
      que.pop();
      deg_order.push_back(a);
      if (a == Tree::root) nodes[a].deg = 0;
      int leaf_flag = true;
      for (int i = 0; i < (int)edges[a].size(); i++) {
        int b = edges[a][i].to;
        if (nodes[b].deg != -1) {
          nodes[a].parent = b;
          nodes[a].eid = edges[a][i].eid;
          nodes[a].cost = edges[a][i].cost;
          nodes[a].deg = nodes[b].deg + 1;
        } else {
          leaf_flag = false;
          nodes[a].childs.push_back(b);
          que.push(b);
        }
      }
      if (leaf_flag) leaves.push_back(a);
    }
    for (int i = (int)n - 1; i >= 0; i--) {
      int a = deg_order[i];
      for (int j = 0; j < (int)nodes[a].childs.size(); j++) {
        int b = nodes[a].childs[j];
        nodes[a].subtree_n += nodes[b].subtree_n;
      }
    }
  }

 public:
  vector<node> nodes;
  vector<int> deg_order;
  vector<int> leaves;
  int root;
  Tree(tree_t T, int root) {
    n = T.n;
    nodes.resize(n);
    for (int i = 0; i < (int)n; i++) {
      nodes[i].id = i;
      nodes[i].val = T.vals[i];
      nodes[i].cost = init_cost;
    }
    edges.resize(n);
    for (int i = 0; i < (int)n - 1; i++) {
      edges[T.edges[i].first].push_back(
          {i, T.edges[i].second,
           ((int)(T.costs.size()) > i ? T.costs[i] : init_cost)});
      edges[T.edges[i].second].push_back(
          {i, T.edges[i].first,
           ((int)(T.costs.size()) > i ? T.costs[i] : init_cost)});
    }
    Tree::root = root;
    tree_construction();
    return;
  }
  vector<long long int> ans;
  Binary_Indexed_Tree *bit;
  void dfs(int id) {
    for (auto fac : nodes[id].val) {
      bit->add(nodes[id].deg + fac.first, fac.second);
    }
    ans[id] = bit->sum(nodes[id].deg, n * 2 + 8);
    for (auto a : nodes[id].childs) {
      dfs(a);
    }
    for (auto fac : nodes[id].val) {
      bit->add(nodes[id].deg + fac.first, -fac.second);
    }
  }
  void solve() {
    ans.resize(n);
    bit = new Binary_Indexed_Tree(vector<long long int>(n * 2 + 10, 0));
    dfs(0);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ;
  tree_t T;
  cin >> T.n;
  for (int i = 0; i < (int)T.n - 1; i++) {
    int s, t;
    cin >> s >> t;
    s--;
    t--;
    T.edges.push_back({s, t});
  }
  T.vals.resize(T.n);
  int q;
  cin >> q;
  for (int i = 0; i < (int)q; i++) {
    int v, d;
    cin >> v >> d;
    v--;
    d = min(d, T.n + 3);
    long long int x;
    cin >> x;
    T.vals[v].push_back({d, x});
  }
  Tree tree(T, 0);
  tree.solve();
  for (int extra_i = 0; extra_i < (int)tree.ans.size(); extra_i++) {
    cout << tree.ans[extra_i] << " ";
  }
  cout << endl;
  ;
}

```