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 MAXN = 100010;
class tPRO {
 public:
  int which, pos;
  tPRO() {}
} property[MAXN];
int n, q, sumArr, countForOne;
vector<int> E[MAXN];
vector<int> Tree[MAXN];
void prepare() {
  sumArr = 1;
  for (int i = 0; i <= n; i++) Tree[1].push_back(0);
  for (int r = 0; r < E[1].size(); r++) {
    int u = E[1][r];
    sumArr++;
    int pos = 1;
    int pre = 1;
    Tree[sumArr].push_back(0);
    for (;;) {
      Tree[sumArr].push_back(0);
      property[u].which = sumArr;
      property[u].pos = pos;
      int v = -1;
      for (int i = 0; i < E[u].size(); i++) {
        if (E[u][i] != pre) v = E[u][i];
      }
      if (v < 0) break;
      pre = u;
      u = v;
      pos++;
    }
  }
}
int Tree_ask(int which, int p) {
  if (which == 1 && p == 0) return countForOne;
  int ans = 0;
  int max = Tree[which].size() - 1;
  for (; p <= max;) {
    ans += Tree[which][p];
    p += p ^ (p & (p - 1));
  }
  return ans;
}
void Tree_modify(int which, int p, int x) {
  for (; p > 0;) {
    Tree[which][p] += x;
    p -= p ^ (p & (p - 1));
  }
}
void Tree_change(int which, int l, int r, int x) {
  if (which == 1 && l == 0) {
    countForOne += x;
    l++;
  }
  if (l > r) return;
  Tree_modify(which, l - 1, -x);
  Tree_modify(which, r, x);
}
void solve() {
  for (int run = 0; run < q; run++) {
    int id;
    scanf("%d", &id);
    if (id == 1) {
      int u;
      scanf("%d", &u);
      int t1, t2;
      if (u == 1) {
        t1 = Tree_ask(1, 0);
        t2 = 0;
      } else {
        t1 = Tree_ask(property[u].which, property[u].pos);
        t2 = Tree_ask(1, property[u].pos);
      }
      printf("%d\n", t1 + t2);
    } else {
      int u, x, d;
      scanf("%d%d%d", &u, &x, &d);
      if (u == 1) {
        Tree_change(1, 0, d, x);
      } else {
        int which = property[u].which;
        int maxr = Tree[which].size() - 1;
        int r = property[u].pos + d;
        int l = property[u].pos - d;
        if (r > maxr) r = maxr;
        if (l > 0) {
          Tree_change(which, l, r, x);
        } else {
          Tree_change(which, 1, r, x);
          Tree_change(1, 0, -l, x);
          if (-l >= 1) Tree_change(which, 1, min(-l, maxr), -x);
        }
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    E[x].push_back(y);
    E[y].push_back(x);
  }
  prepare();
  solve();
  return 0;
}
