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 N = 100000;
int n, q, ans[N], level[N], cnt;
array<int, 2> pos[N];
vector<int> adj[N], nodes[N];
void dfs(int x, int pr, int lvl) {
  level[x] = lvl;
  if (x != 0) {
    nodes[cnt].push_back(x);
  }
  for (auto e : adj[x]) {
    if (e != pr) {
      dfs(e, x, lvl + 1);
      if (x == 0) {
        cnt++;
      }
    }
  }
}
inline int dist(int x, int y) {
  if (pos[x][0] == pos[y][0]) return abs(level[x] - level[y]);
  return level[x] + level[y];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q;
  int root_q = sqrt(q);
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  dfs(0, -1, 0);
  vector<vector<int>> pref(cnt);
  vector<int> pref_gen(n, 0);
  for (int i = 0; i < cnt; i++) {
    pref[i] = vector<int>((int)nodes[i].size(), 0);
    for (int j = 0; j < (int)nodes[i].size(); j++) {
      pos[nodes[i][j]] = {i, j};
    }
  }
  vector<tuple<int, int, int>> upd;
  auto compute = [&]() {
    for (int i = n - 2; i > 0; i--) {
      pref_gen[i] += pref_gen[i + 1];
    }
    for (auto e : upd) {
      int v, x, d;
      tie(v, x, d) = e;
      if (level[v] <= d) {
        ans[0] += x;
      }
      if (v == 0) continue;
      int mx = min(pos[v][1] + d, (int)nodes[pos[v][0]].size() - 1);
      int mn = max(pos[v][1] - d - 1, -1);
      int done =
          min((int)nodes[pos[v][0]].size() - 1, max(d - level[v] - 1, -1));
      if (done != -1) {
        pref[pos[v][0]][done] -= x;
      }
      if (mn != -1) {
        pref[pos[v][0]][mn] -= x;
      }
      pref[pos[v][0]][mx] += x;
    }
    for (int i = 0; i < cnt; i++) {
      int sm = 0;
      for (int j = (int)nodes[i].size() - 1; j >= 0; j--) {
        sm += pref[i][j];
        pref[i][j] = 0;
        ans[nodes[i][j]] += pref_gen[j + 1] + sm;
      }
    }
    for (int i = 0; i < n; i++) {
      pref_gen[i] = 0;
    }
    upd.clear();
  };
  while (q--) {
    int t;
    cin >> t;
    if (t == 0) {
      int v, x, d;
      cin >> v >> x >> d;
      v--;
      upd.emplace_back(v, x, d);
      if (d - level[v] > 0) {
        pref_gen[d - level[v]] += x;
      }
    } else {
      int v;
      cin >> v;
      v--;
      int res = ans[v];
      for (auto e : upd) {
        int ver, x, d;
        tie(ver, x, d) = e;
        if (dist(v, ver) <= d) {
          res += x;
        }
      }
      cout << res << '\n';
    }
    if ((int)upd.size() >= root_q) {
      compute();
    }
  }
  return 0;
}
