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 = 1e5 + 100;
int tot;
struct node {
  int urt, subrt, dis;
};
struct BIT {
  vector<long long> c;
  int _n;
  void init(int x) {
    _n = x + 4;
    c.clear();
    c.resize(_n + 2);
  }
  void add(int x, long long val) {
    if (x <= 0) return;
    if (x > _n) x = _n;
    while (x) {
      c[x] += val;
      x -= x & -x;
    }
  }
  long long query(int x) {
    long long ret = 0;
    while (x <= _n) {
      ret += c[x];
      x += x & -x;
    }
    return ret;
  }
} tr[N << 1];
vector<node> vt[N];
int vis[N];
const int inf = 1e9;
int rt, mx, _size, siz[N];
int h[N], nex[N << 1], to[N << 1], cur;
void add_edge(int x, int y) {
  to[++cur] = y;
  nex[cur] = h[x];
  h[x] = cur;
}
void getrt(int u, int fa) {
  siz[u] = 1;
  int num = 0;
  for (int i = h[u]; i; i = nex[i]) {
    int v = to[i];
    if (v == fa || vis[v]) continue;
    getrt(v, u);
    siz[u] += siz[v];
    num = max(num, siz[v]);
  }
  num = max(num, _size - siz[u]);
  if (mx > num) mx = num, rt = u;
}
void getinfo(int u, int fa, int urt, int subrt, int dis) {
  vt[u].push_back({urt, subrt, dis});
  for (int i = h[u]; i; i = nex[i]) {
    int v = to[i];
    if (vis[v] || v == fa) continue;
    getinfo(v, u, urt, subrt, dis + 1);
  }
}
void divide(int u) {
  vis[u] = 1;
  int urt = ++tot;
  getrt(u, 0);
  vt[u].push_back({urt, 0, 0});
  tr[urt].init(siz[u]);
  for (int i = h[u]; i; i = nex[i]) {
    int v = to[i];
    if (vis[v]) continue;
    tr[++tot].init(siz[v]);
    getinfo(v, u, urt, tot, 1);
  }
  for (int i = h[u]; i; i = nex[i]) {
    int v = to[i];
    if (vis[v]) continue;
    mx = inf;
    _size = siz[v];
    getrt(v, u);
    divide(rt);
  }
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    add_edge(x, y);
    add_edge(y, x);
  }
  mx = inf;
  _size = n;
  getrt(1, 0);
  divide(rt);
  for (int i = 1; i <= q; i++) {
    int op, v, x, d;
    scanf("%d%d", &op, &v);
    if (op == 0) {
      scanf("%d%d", &x, &d);
      for (int i = 0; i < vt[v].size(); i++) {
        node gg = vt[v][i];
        tr[gg.urt].add(d - gg.dis + 1, x);
        if (gg.subrt) tr[gg.subrt].add(d - gg.dis + 1, -x);
      }
    } else {
      long long ret = 0;
      for (int i = 0; i < vt[v].size(); i++) {
        node gg = vt[v][i];
        ret += tr[gg.urt].query(gg.dis + 1);
        if (gg.subrt) ret += tr[gg.subrt].query(gg.dis + 1);
      }
      printf("%lld\n", ret);
    }
  }
  return 0;
}
