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;
int ma(int a, int b) { return ((a - b > 0) ? a : b); }
int mi(int a, int b) { return ((a - b > 0) ? b : a); }
struct T {
  int val;
  T() {}
  T(int &val) : val(val) {}
  inline void clear() { val = 0; }
};
struct ST {
  int lazy[4 * 100050], ar[100050];
  T tree[4 * 100050];
  int n;
  ST() {}
  inline T Op(T &val1, T &val2) {
    T ty;
    ty.val = val1.val + val2.val;
    return ty;
  }
  inline void updatepro(int laz, int id, int l, int r) {
    if (laz != 0) {
      int ta = r - l;
      tree[id].val += laz * ta;
      lazy[id] += laz;
    }
  }
  inline void proh(int id, int l, int r) {
    int mid = (l + r) >> 1;
    updatepro(lazy[id], id << 1, l, mid);
    updatepro(lazy[id], id << 1 | 1, mid, r);
    lazy[id] = 0;
  }
  inline void updateRange(int x, int y, int val, int id, int l, int r) {
    if (x >= r || y <= l) return;
    if (x <= l && r <= y) {
      updatepro(val, id, l, r);
      return;
    }
    proh(id, l, r);
    int mid = (l + r) >> 1;
    updateRange(x, y, val, id << 1, l, mid);
    updateRange(x, y, val, id << 1 | 1, mid, r);
    tree[id] = Op(tree[id << 1], tree[id << 1 | 1]);
  }
  inline T getSum(int x, int y, int id, int l, int r) {
    if (x >= r || l >= y) {
      T ans;
      ans.clear();
      return ans;
    }
    if (x <= l && r <= y) return tree[id];
    proh(id, l, r);
    int mid = (l + r) >> 1;
    T ez, ez1, ez2;
    ez1 = getSum(x, y, id << 1, l, mid);
    ez2 = getSum(x, y, id << 1 | 1, mid, r);
    ez = Op(ez1, ez2);
    return ez;
  }
  inline void build1(int id, int l, int r) {
    if (r - l < 2) {
      tree[id].val = ar[l];
      return;
    }
    int mid = (l + r) >> 1;
    build1(id << 1, l, mid);
    build1(id << 1 | 1, mid, r);
    tree[id] = Op(tree[id << 1], tree[id << 1 | 1]);
  }
  inline void upd(int x, int y, int val) { updateRange(x, y, val, 1, 0, n); }
  inline void build() { build1(1, 0, n); }
  inline T que(int x, int y) { return getSum(x, y, 1, 0, n); }
} st1, st2;
int k1 = 0, lv = 1;
int ni[100050], d[100050], pos1[100050];
vector<int> v1, v2;
vector<int> adj[100050];
vector<int> eu;
int pos[100050];
int cnt = -1;
int p[100050][21], tsz[100050], dp[100050], vis[100050];
inline int make(int u, int par, int lvl) {
  cnt++;
  tsz[u] = 1;
  p[u][0] = par;
  eu.push_back(u);
  pos[u] = cnt;
  for (auto v : adj[u])
    if (v != par) tsz[u] += make(v, u, lvl + 1);
  return tsz[u];
}
inline void bfs(int u) {
  queue<int> q;
  q.push(u);
  v1.push_back(u);
  k1++;
  ni[lv++] = k1;
  d[u] = 1;
  pos1[u] = 0;
  while (!q.empty()) {
    int t = q.front();
    q.pop();
    for (auto v : adj[t]) {
      if (v != p[t][0]) {
        q.push(v);
        d[v] = d[t] + 1;
        if (d[v] != lv) ni[lv++] = k1;
        pos1[v] = k1++;
      }
    }
  }
}
inline int solve(int al, int &ve) {
  al--;
  if (al == 0) return ve;
  for (int(i) = (0); (i) < (100); (i)++) {
    for (int(j) = (0); (j) < (21); (j)++) {
      if (al - dp[j] < 0) {
        ve = p[ve][j - 1];
        al = al - dp[j - 1];
        break;
      }
    }
    if (al == 0) break;
  }
  return ve;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  int n, q;
  cin >> n >> q;
  for (int(i) = (0); (i) < (n - 1); (i)++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int pe = make(0, -1, 1);
  bfs(0);
  for (int(i) = (lv); (i) < (1e5); (i)++) ni[i] = k1;
  st1.n = n;
  st2.n = n;
  for (int(i) = (0); (i) < (21 + 1); (i)++)
    dp[i] = (i == 0) ? 1 : 2 * dp[i - 1];
  for (int(i) = (0); (i) < (21 - 1); (i)++)
    for (int(j) = (0); (j) < (n); (j)++)
      if (p[j][i] != -1) p[j][i + 1] = p[p[j][i]][i];
  int type, v, x, di, r, al;
  for (int(i) = (0); (i) < (q); (i)++) {
    cin >> type;
    if (type == 0) {
      cin >> v >> x >> di;
      v--;
      if (v == 0) st1.upd(0, ni[di + 1], x);
      if (v != 0) {
        al = d[v], r = mi(pos[v] + di + 1, pos[v] + tsz[v]);
        if (di + 1 >= al) {
          di -= al;
          di += 2;
          st1.upd(0, ni[di], x);
          v = eu[pos[v] + tsz[v] - 1];
          if (d[v] - di > 0) v = solve(d[v] - di, v), st2.upd(pos[v], r, x);
        } else
          v = solve(di + 1, v), st2.upd(pos[v], r, x);
      }
    }
    if (type == 1) {
      cin >> v;
      v--;
      cout << st1.que(pos1[v], pos1[v] + 1).val +
                  st2.que(pos[v], pos[v] + 1).val
           << endl;
    }
  }
  return 0;
}
