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;
bool ok = false;
class seg {
 private:
 public:
  vector<long long int> a;
  long long int ss;
  void add(long long int index) { ss++; }
  seg() { ss = 0; }
  void space() {
    a.resize(4 * ss + 10);
    fill(a.begin(), a.end(), 0);
  }
  void check(long long int node) {
    a[node * 2] += a[node];
    a[node * 2 + 1] += a[node];
    a[node] = 0;
  }
  long long int query(long long int node, long long int x, long long int y,
                      long long int index) {
    if (ok) {
    }
    if (x == y) {
      return a[node];
    }
    if (a[node] != 0) check(node);
    long long int mid = (x + y) / 2;
    if (index <= mid) {
      return query(2 * node, x, mid, index);
    }
    return query(2 * node + 1, mid + 1, y, index);
  }
  void update(long long int node, long long int x, long long int y,
              long long int sx, long long int sy, long long int value) {
    if (sx < 0 || sy < 0 || sx >= ss || sy >= ss) return;
    if (sx > sy) return;
    if (x > y) {
      return;
    }
    if (sy < x || sx > y) {
      return;
    }
    if (sx <= x && sy >= y) {
      a[node] += value;
      return;
    }
    long long int mid = (x + y) / 2;
    if (a[node] != 0) {
      check(node);
    }
    update(node * 2, x, mid, sx, sy, value);
    update(node * 2 + 1, mid + 1, y, sx, sy, value);
  }
};
vector<seg> segment;
seg common;
vector<vector<long long int> > a;
long long int parent[100009];
long long int level[100009];
long long int n;
void dfs(long long int x) {
  long long int i;
  for (i = (0); i < (a[x].size()); ++i) {
    long long int y = a[x][i];
    if (parent[x] == y) continue;
    parent[y] = x;
    level[y] = level[x] + 1;
    dfs(y);
  }
}
long long int which[100009];
long long int where[100009];
long long int ssize[100009];
long long int chain;
void dd(long long int x) {
  which[x] = chain;
  where[x] = ssize[chain]++;
  segment[chain].add(0);
  long long int i;
  for (i = (0); i < (a[x].size()); ++i) {
    long long int y = a[x][i];
    if (y == parent[x]) continue;
    dd(y);
  }
}
void pp() {
  long long int i;
  cout << endl;
  for (i = (0); i < (chain); ++i) {
    cout << ssize[i] << "  -- " << segment[i].query(1, 0, 0, 0) << endl;
  }
  cout << endl;
  for (i = (0); i < (4); ++i) {
    cout << common.query(1, 0, common.ss - 1, i) << " ";
  }
  cout << endl;
}
int main() {
  long long int m;
  cin >> n >> m;
  long long int i;
  a.resize(n);
  for (i = (0); i < (n - 1); ++i) {
    long long int x, y;
    cin >> x >> y;
    x--;
    y--;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  segment.resize(n + 10);
  level[0] = 0;
  parent[0] = 0;
  dfs(0);
  for (i = (0); i < (a[0].size()); ++i) {
    dd(a[0][i]);
    chain++;
  }
  for (i = (0); i < (chain + 4); ++i) {
    segment[i].space();
  }
  common.ss = n + 10;
  common.space();
  while (m--) {
    long long int flag;
    cin >> flag;
    if (flag == 0) {
      long long int v, x, d;
      cin >> v >> x >> d;
      v--;
      if (v == 0) {
        common.update(1, 0, common.ss - 1, 0, d, x);
        continue;
      }
      segment[which[v]].update(1, 0, segment[which[v]].ss - 1, where[v],
                               min(segment[which[v]].ss - 1, where[v] + d), x);
      segment[which[v]].update(1, 0, segment[which[v]].ss - 1,
                               max(0LL, where[v] - d), where[v] - 1, x);
      long long int left = 0;
      if (where[v] < d) {
        left = d - where[v];
        common.update(1, 0, common.ss - 1, 0, left - 1, x);
        if (left >= 2) {
          segment[which[v]].update(1, 0, segment[which[v]].ss - 1, 0,
                                   min(left - 2, segment[which[v]].ss - 1), -x);
        }
      }
      continue;
    }
    long long int x;
    cin >> x;
    x--;
    if (x == 0) {
      cout << common.query(1, 0, common.ss - 1, 0) << endl;
      continue;
    }
    long long int total;
    total = segment[which[x]].query(1, 0, ssize[which[x]] - 1, where[x]);
    total += common.query(1, 0, common.ss - 1, where[x] + 1);
    cout << total << endl;
  }
  return 0;
}
