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 = 2e5 + 10;
int tot, cnt;
int fir[N], dep[N], col[N], h[N];
struct edge {
  int to;
  int nxt;
} e[2 * N];
inline void add(int x, int y) {
  e[++tot].to = y;
  e[tot].nxt = fir[x];
  fir[x] = tot;
  e[++tot].to = x;
  e[tot].nxt = fir[y];
  fir[y] = tot;
}
inline void dfs(int p, int fa) {
  dep[p] = dep[fa] + 1;
  for (int i = fir[p]; i; i = e[i].nxt)
    if (e[i].to != fa) dfs(e[i].to, p);
  col[p] = cnt, h[cnt] = max(h[cnt], dep[p]);
}
struct tree {
  int val[4 * N];
  inline void pushdown(int p) {
    if (val[p]) {
      val[p * 2] += val[p];
      val[p * 2 + 1] += val[p];
      val[p] = 0;
    }
  }
  inline void change(int p, int left, int right, int l, int r, int c) {
    if (l > r) return;
    if (l <= left && r >= right) {
      val[p] += c;
      return;
    }
    pushdown(p);
    int mid = (left + right) / 2;
    if (l <= mid) change(p * 2, left, mid, l, r, c);
    if (r > mid) change(p * 2 + 1, mid + 1, right, l, r, c);
  }
  inline int query(int p, int left, int right, int pos) {
    if (left == right) return val[p];
    pushdown(p);
    int mid = (left + right) / 2;
    if (pos <= mid)
      return query(p * 2, left, mid, pos);
    else
      return query(p * 2 + 1, mid + 1, right, pos);
  }
} t1, t2;
int main() {
  int n, m, opt, a, b, c, maxn = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &a, &b);
    add(a, b);
  }
  for (int i = fir[1]; i; i = e[i].nxt) {
    int q = e[i].to;
    cnt++, dfs(q, 1);
    maxn = max(maxn, h[cnt]);
  }
  n = cnt * maxn + 1;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &opt, &a);
    if (opt) {
      if (a == 1) {
        printf("%d\n", t1.query(1, 1, n, 1) + t2.query(1, 1, n, 1));
        continue;
      }
      int id1 = 1 + (col[a] - 1) * maxn + dep[a];
      int id2 = 1 + (dep[a] - 1) * cnt + col[a];
      printf("%d\n", t1.query(1, 1, n, id1) + t2.query(1, 1, n, id2));
    } else {
      scanf("%d%d", &c, &b);
      if (a == 1) {
        t2.change(1, 1, n, 1, min(1 + b * cnt, n), c);
        continue;
      }
      int id1 = 1 + (col[a] - 1) * maxn + dep[a];
      int id2 = 1 + (col[a] - 1) * maxn + (b - dep[a]);
      int len = 1 + col[a] * maxn;
      if (dep[a] > b)
        t1.change(1, 1, n, id1 - b, min(id1 + b, len), c);
      else {
        t1.change(1, 1, n, id2 + 1, min(id1 + b, len), c);
        t2.change(1, 1, n, 1, min(1 + (b - dep[a]) * cnt, n), c);
      }
    }
  }
  return 0;
}
