A little girl loves problems on trees very much. Here's one of them.

A tree is an undirected connected graph, not containing cycles. The degree of node x in the tree is the number of nodes y of the tree, such that each of them is connected with node x by some edge of the tree. 

Let's consider a tree that consists of n nodes. We'll consider the tree's nodes indexed from 1 to n. The cosidered tree has the following property: each node except for node number 1 has the degree of at most 2.

Initially, each node of the tree contains number 0. Your task is to quickly process the requests of two types:

  * Request of form: 0 v x d. In reply to the request you should add x to all numbers that are written in the nodes that are located at the distance of at most d from node v. The distance between two nodes is the number of edges on the shortest path between them. 
  * Request of form: 1 v. In reply to the request you should print the current number that is written in node v. 

Input

The first line contains integers n (2 ≤ n ≤ 105) and q (1 ≤ q ≤ 105) — the number of tree nodes and the number of requests, correspondingly.

Each of the next n - 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), that show that there is an edge between nodes ui and vi. Each edge's description occurs in the input exactly once. It is guaranteed that the given graph is a tree that has the property that is described in the statement.

Next q lines describe the requests.

  * The request to add has the following format: 0 v x d (1 ≤ v ≤ n, 1 ≤ x ≤ 104, 1 ≤ d < n). 
  * The request to print the node value has the following format: 1 v (1 ≤ v ≤ n). 



The numbers in the lines are separated by single spaces.

Output

For each request to print the node value print an integer — the reply to the request.

Examples

Input

3 6
1 2
1 3
0 3 1 2
0 2 3 1
0 1 5 2
1 1
1 2
1 3


Output

9
9
6


Input

6 11
1 2
2 5
5 4
1 6
1 3
0 3 1 3
0 3 4 5
0 2 1 4
0 1 5 5
0 4 6 2
1 1
1 2
1 3
1 4
1 5
1 6


Output

11
17
11
16
17
11
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5;
int n, q;
int chain = 1;
int whichchain[MAXN];
vector<int> g[MAXN];
vector<pair<int, int> > v;
int chainBegin[MAXN], chainEnd[MAXN], chainindex[MAXN];
int treeindex[MAXN];
int leveltree[MAXN];
int maxlevel;
int level[MAXN], levelend[MAXN], levelindex[MAXN];
int t1, t2;
int chaintree[4 * MAXN];
int Cpush[4 * MAXN], Lpush[4 * MAXN];
void dfs(int x, int p, int c) {
  int tmp = t1 + 1;
  if (p == -1) {
    level[x] = 0;
  } else {
    level[x] = level[p] + 1;
  }
  v.push_back(make_pair(level[x], x));
  maxlevel = max(maxlevel, level[x]);
  t1++;
  chainEnd[c] = t1;
  chainindex[x] = t1;
  whichchain[x] = c;
  for (auto i : g[x]) {
    if (i != p) {
      if (p == -1) {
        dfs(i, x, ++chain);
      } else {
        dfs(i, x, c);
      }
    }
  }
  chainBegin[c] = tmp;
}
inline void chainpush(int x, int l, int r) {
  chaintree[x] += (r - l + 1) * Cpush[x];
  if (l != r) {
    Cpush[x + x] += Cpush[x];
    Cpush[x + x + 1] += Cpush[x];
  }
  Cpush[x] = 0;
}
void upd(int x, int l, int r, int TL, int TR, int c) {
  chainpush(x, l, r);
  if (r < TL || TR < l) {
    return;
  }
  if (TL <= l && r <= TR) {
    Cpush[x] += c;
    chainpush(x, l, r);
    return;
  }
  int m = (l + r) / 2;
  upd(x + x, l, m, TL, TR, c);
  upd(x + x + 1, m + 1, r, TL, TR, c);
  chaintree[x] = chaintree[x + x] + chaintree[x + x + 1];
}
int sum(int x, int l, int r, int TL, int TR) {
  chainpush(x, l, r);
  if (r < TL || TR < l) {
    return 0;
  }
  if (TL <= l && r <= TR) {
    return chaintree[x];
  }
  int m = (l + r) / 2;
  return sum(x + x, l, m, TL, TR) + sum(x + x + 1, m + 1, r, TL, TR);
}
inline void levelpush(int x, int l, int r) {
  leveltree[x] += (r - l + 1) * Lpush[x];
  if (l != r) {
    Lpush[x + x] += Lpush[x];
    Lpush[x + x + 1] += Lpush[x];
  }
  Lpush[x] = 0;
}
void upd2(int x, int l, int r, int TL, int TR, int c) {
  levelpush(x, l, r);
  if (r < TL || TR < l) {
    return;
  }
  if (TL <= l && r <= TR) {
    Lpush[x] += c;
    levelpush(x, l, r);
    return;
  }
  int m = (l + r) / 2;
  upd2(x + x, l, m, TL, TR, c);
  upd2(x + x + 1, m + 1, r, TL, TR, c);
  leveltree[x] = leveltree[x + x] + leveltree[x + x + 1];
}
int sum2(int x, int l, int r, int TL, int TR) {
  levelpush(x, l, r);
  if (r < TL || TR < l) {
    return 0;
  }
  if (TL <= l && r <= TR) {
    return leveltree[x];
  }
  int m = (l + r) / 2;
  return sum2(x + x, l, m, TL, TR) + sum2(x + x + 1, m + 1, r, TL, TR);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, -1, 1);
  sort(v.begin(), v.end());
  for (int i = 0; i < v.size(); i++) {
    levelend[v[i].first] = i + 1;
    levelindex[v[i].second] = i + 1;
  }
  for (int i = 1; i <= q; i++) {
    int x;
    cin >> x;
    if (!x) {
      int vv, d;
      cin >> x >> vv >> d;
      if (x == 1) {
        upd2(1, 1, n, 1, levelend[min(d, maxlevel)], vv);
      } else {
        int c = whichchain[x];
        upd(1, 1, n, max(chainBegin[c], chainindex[x] - d),
            min(chainindex[x] + d, chainEnd[c]), vv);
        if (d >= level[x]) {
          upd2(1, 1, n, 1, levelend[min(d - level[x], maxlevel)], vv);
          d -= level[x] + 1;
          if (d >= 0) {
            upd(1, 1, n, chainBegin[c], min(chainBegin[c] + d, chainEnd[c]),
                -vv);
          }
        }
      }
    } else {
      cin >> x;
      cout << sum(1, 1, n, chainindex[x], chainindex[x]) +
                  sum2(1, 1, n, levelindex[x], levelindex[x])
           << '\n';
    }
  }
  return 0;
}
