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<vector<int> > v, t, z;
int M, X;
void add_y(int vx, int vy, int tly, int try_, int ly, int ry) {
  if (ly > ry) return;
  if (tly == ly && try_ == ry) {
    t[vx][vy] += X;
  } else {
    int tmy = (tly + try_) / 2;
    add_y(vx, 2 * vy, tly, tmy, ly, min(ry, tmy));
    add_y(vx, 2 * vy + 1, tmy + 1, try_, max(ly, tmy + 1), ry);
  }
}
void add_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
  if (lx > rx) return;
  if (tlx == lx && trx == rx)
    add_y(vx, 1, 0, M - 1, ly, ry);
  else {
    int tmx = (tlx + trx) / 2;
    add_x(2 * vx, tlx, tmx, lx, min(rx, tmx), ly, ry);
    add_x(2 * vx + 1, tmx + 1, trx, max(tmx + 1, lx), rx, ly, ry);
  }
}
void update_y(int vx, int tlx, int trx, int vy, int tly, int try_, int lx,
              int rx, int ly, int ry) {
  if (ly > ry) return;
  if (tly == try_) {
    if (tlx == trx)
      t[vx][vy] += X;
    else
      t[vx][vy] = max(t[vx * 2][vy], t[vx * 2 + 1][vy]);
  } else {
    int tmy = (tly + try_) / 2;
    update_y(vx, lx, rx, vy * 2, tly, tmy, lx, rx, ly, min(ry, tmy));
    update_y(vx, lx, rx, vy * 2 + 1, tmy + 1, try_, lx, rx, max(ly, tmy + 1),
             ry);
    t[vx][vy] = max(t[vx][vy * 2], t[vx][vy * 2 + 1]);
  }
}
void update_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
  if (lx > rx) return;
  if (lx != rx) {
    int tmx = (tlx + trx) / 2;
    update_x(vx * 2, tlx, tmx, lx, min(rx, tmx), ly, ry);
    update_x(vx * 2 + 1, tmx + 1, trx, max(lx, tmx + 1), rx, ly, ry);
  }
  update_y(vx, tlx, trx, 1, 0, M - 1, lx, rx, ly, ry);
}
int fin_y(int vx, int vy, int tly, int try_, int xx, int yy) {
  int R = t[vx][vy];
  while (tly < try_) {
    int tmy = (tly + try_) / 2;
    if (yy <= tmy) {
      try_ = tmy;
      vy = 2 * vy;
      R += t[vx][vy];
    } else {
      tly = tmy + 1;
      vy = 2 * vy + 1;
      R += t[vx][vy];
    }
  }
  return R;
}
int fin_x(int vx, int tlx, int trx, int xx, int yy) {
  int R = fin_y(vx, 1, 0, M - 1, xx, yy);
  while (tlx < trx) {
    int tmx = (tlx + trx) / 2;
    if (xx <= tmx) {
      trx = tmx;
      vx = 2 * vx;
      R += fin_y(vx, 1, 0, M - 1, xx, yy);
    } else {
      tlx = tmx + 1;
      vx = 2 * vx + 1;
      R += fin_y(vx, 1, 0, M - 1, xx, yy);
    }
  }
  return R;
}
struct pnt {
  int x, y;
};
pnt q[100005];
int main() {
  int n, Q;
  cin >> n >> Q;
  z.resize(n);
  for (int i = 1, a, b; i < n; ++i) {
    cin >> a >> b;
    --a;
    --b;
    z[a].push_back(b);
    z[b].push_back(a);
  }
  v.resize(z[0].size());
  for (int i = 0; i < z[0].size(); ++i) {
    v[i].push_back(z[0][i]);
    q[z[0][i]].x = i;
    q[z[0][i]].y = 0;
  }
  bool tt = true;
  int xz = z[0].size(), T0 = 0;
  while (tt) {
    tt = false;
    for (int i = 0; i < z[0].size(); ++i) {
      int l = v[i].back();
      if (z[l].size() > 1) {
        tt = true;
        if (z[l][0] == 0 || z[l][0] == v[i][v[i].size() - 2]) {
          q[z[l][1]].x = i;
          q[z[l][1]].y = v[i].size();
          v[i].push_back(z[l][1]);
        } else {
          q[z[l][0]].x = i;
          q[z[l][0]].y = v[i].size();
          v[i].push_back(z[l][0]);
        }
      }
    }
  }
  for (int i = 0; i < xz; ++i)
    if (M < v[i].size()) M = v[i].size();
  t.assign(4 * xz, vector<int>(4 * M, 0));
  for (int i = 0, c, vv; i < Q; ++i) {
    cin >> c >> vv;
    --vv;
    int cux = q[vv].x;
    int cuy = q[vv].y;
    if (c == 0) {
      int x, d;
      cin >> x >> d;
      X = x;
      if (!vv) {
        T0 += x;
        add_x(1, 0, xz - 1, 0, xz - 1, 0, min(d - 1, M - 1));
      } else {
        if (cuy - d >= -1) {
          add_x(1, 0, xz - 1, cux, cux, max(0, cuy - d), min(cuy + d, M - 1));
          if (cuy - d == -1) T0 += x;
        } else {
          T0 += x;
          if (cux) add_x(1, 0, xz - 1, 0, cux - 1, 0, min(d - cuy - 2, M - 1));
          if (cux + 1 < xz)
            add_x(1, 0, xz - 1, cux + 1, xz - 1, 0, min(d - cuy - 2, M - 1));
          add_x(1, 0, xz - 1, cux, cux, 0, min(cuy + d, M - 1));
        }
      }
    } else {
      if (!vv)
        cout << T0 << endl;
      else
        cout << fin_x(1, 0, xz - 1, cux, cuy) << endl;
    }
  }
  return 0;
}
