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;
vector<long long> v[100002];
long long lst[100002];
long long d[100002];
long long in2[100002];
long long pa[100002];
long long mxd[100002];
long long in1[100002];
long long ptr = -1;
long long lsd = 0;
void dfs(long long x, long long p) {
  mxd[x] = d[x];
  in2[x] = ++ptr;
  pa[x] = p;
  for (auto y : v[x])
    if (y != p) d[y] = d[x] + 1, dfs(y, x), mxd[x] = max(mxd[x], mxd[y]);
  lsd = max(lsd, d[x]);
}
void bfs() {
  queue<long long> q;
  long long f = -1;
  q.push(0);
  while (1) {
    if (q.empty()) break;
    long long x = q.front();
    q.pop();
    in1[x] = ++f;
    lst[d[x]] = max(lst[d[x]], f);
    for (auto y : v[x])
      if (y != pa[x]) q.push(y);
  }
}
long long bfstree[4 * 100002], bfslzy[4 * 100002], dfstree[4 * 100002],
    dfslzy[4 * 100002];
void bfspush(long long nd, long long lo, long long hi) {
  bfstree[nd] += bfslzy[nd];
  if (lo != hi)
    bfslzy[nd + nd] += bfslzy[nd], bfslzy[nd + nd + 1] += bfslzy[nd];
  bfslzy[nd] = 0;
}
void bfsupdate(long long nd, long long lo, long long hi, long long l,
               long long r, long long x) {
  if (bfslzy[nd]) bfspush(nd, lo, hi);
  if (lo > r or hi < l) return;
  if (lo >= l and hi <= r) {
    bfslzy[nd] = x, bfspush(nd, lo, hi);
    return;
  }
  long long md = (lo + hi) / 2;
  bfsupdate(nd + nd, lo, md, l, r, x);
  bfsupdate(nd + nd + 1, md + 1, hi, l, r, x);
  bfstree[nd] = bfstree[nd + nd] + bfstree[nd + nd + 1];
}
long long bfsquery(long long nd, long long lo, long long hi, long long l,
                   long long r) {
  if (bfslzy[nd]) bfspush(nd, lo, hi);
  if (lo > r or hi < l) return 0;
  if (lo >= l and hi <= r) {
    return bfstree[nd];
  }
  long long md = (lo + hi) / 2;
  return bfsquery(nd + nd, lo, md, l, r) +
         bfsquery(nd + nd + 1, md + 1, hi, l, r);
}
void dfspush(long long nd, long long lo, long long hi) {
  dfstree[nd] += dfslzy[nd];
  if (lo != hi)
    dfslzy[nd + nd] += dfslzy[nd], dfslzy[nd + nd + 1] += dfslzy[nd];
  dfslzy[nd] = 0;
}
void dfsupdate(long long nd, long long lo, long long hi, long long l,
               long long r, long long x) {
  if (dfslzy[nd]) dfspush(nd, lo, hi);
  if (lo > r or hi < l) return;
  if (lo >= l and hi <= r) {
    dfslzy[nd] = x, dfspush(nd, lo, hi);
    return;
  }
  long long md = (lo + hi) / 2;
  dfsupdate(nd + nd, lo, md, l, r, x);
  dfsupdate(nd + nd + 1, md + 1, hi, l, r, x);
  dfstree[nd] = dfstree[nd + nd] + dfstree[nd + nd + 1];
}
long long dfsquery(long long nd, long long lo, long long hi, long long l,
                   long long r) {
  if (dfslzy[nd]) dfspush(nd, lo, hi);
  if (lo > r or hi < l) return 0;
  if (lo >= l and hi <= r) {
    return dfstree[nd];
  }
  long long md = (lo + hi) / 2;
  return dfsquery(nd + nd, lo, md, l, r) +
         dfsquery(nd + nd + 1, md + 1, hi, l, r);
}
signed main() {
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long n, q;
  cin >> n >> q;
  for (long long i = 1; i <= n - 1; i++) {
    long long x, y;
    cin >> x >> y;
    x--;
    y--;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  dfs(0, -1);
  bfs();
  long long flaw = 0;
  while (q--) {
    long long t;
    cin >> t;
    if (t == 0) {
      long long vv, x, dd;
      cin >> vv >> x >> dd;
      vv--;
      if (vv == 0) {
        bfsupdate(1, 0, n - 1, 1, lst[min(lsd, dd)], x);
        flaw += x;
        continue;
      }
      long long z = in2[vv] + min(dd, mxd[vv] - d[vv]);
      if (dd < d[vv]) {
        dfsupdate(1, 0, n - 1, in2[vv] - dd, z, x);
        continue;
      }
      if (dd == d[vv]) {
        dfsupdate(1, 0, n - 1, in2[vv] - dd + 1, z, x);
        flaw += x;
        continue;
      }
      long long bkc = min(lsd, dd - d[vv]);
      bfsupdate(1, 0, n - 1, 1, lst[bkc], x);
      flaw += x;
      if (bkc + 1 <= z) dfsupdate(1, 0, n - 1, in2[vv] + bkc + 1 - d[vv], z, x);
    } else {
      long long x;
      cin >> x;
      x--;
      if (x == 0)
        cout << flaw << "\n";
      else
        cout << dfsquery(1, 0, n - 1, in2[x], in2[x]) +
                    bfsquery(1, 0, n - 1, in1[x], in1[x])
             << "\n";
    }
  }
}
