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 INF = 0x7f7f7f7f;
const int mo = 1e9 + 7;
int n, q, head[100005], tot, dep[100005], idx;
int dfn[100005], f[100005][20], son[100005][20];
struct edge {
  int to, nxt;
} e[100005 << 1];
void addEdge(int u, int v) {
  e[++tot] = (edge){v, head[u]};
  head[u] = tot;
}
void dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  f[u][0] = fa;
  dfn[u] = ++idx;
  son[u][0] = son[fa][0] = u;
  for (int i = 1; i < 18; i++) f[u][i] = f[f[u][i - 1]][i - 1];
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].to != fa) dfs(e[i].to, u);
  for (int i = 1; i < 18; i++) son[u][i] = son[son[u][i - 1]][i - 1];
}
struct SegmentTree {
  int val[100005 << 2], lzy[100005 << 2];
  void pushdown(int rt) {
    if (!lzy[rt]) return;
    val[rt << 1] += lzy[rt];
    val[rt << 1 | 1] += lzy[rt];
    lzy[rt << 1] += lzy[rt];
    lzy[rt << 1 | 1] += lzy[rt];
    lzy[rt] = 0;
  }
  void insert(int rt, int l, int r, int al, int ar, int aw) {
    if (l > r || al > r || ar < l) return;
    if (al <= l && r <= ar) {
      if (l == r) val[rt] += aw;
      lzy[rt] += aw;
      return;
    }
    int mid = l + r >> 1;
    pushdown(rt);
    val[rt] = 0;
    if (al <= mid) insert(rt << 1, l, mid, al, ar, aw);
    if (ar > mid) insert(rt << 1 | 1, mid + 1, r, al, ar, aw);
  }
  int query(int rt, int l, int r, int ai) {
    if (l > r || l > ai || r < ai) return 0;
    if (l == r) return val[rt];
    int mid = l + r >> 1;
    pushdown(rt);
    val[rt] = 0;
    if (mid >= ai) return query(rt << 1, l, mid, ai);
    return query(rt << 1 | 1, mid + 1, r, ai);
  }
  void search(int rt, int l, int r) {
    if (l == r) {
      printf("%d:%d\n", l, val[rt]);
      return;
    }
    int mid = l + r >> 1;
    pushdown(rt);
    search(rt << 1, l, mid);
    search(rt << 1 | 1, mid + 1, r);
  }
} Chain, Depth;
int findSon(int u, int dp) {
  for (int i = 17; i >= 0; i--)
    if (dp >= (1 << i)) u = son[u][i], dp -= (1 << i);
  return u;
}
int findFa(int u, int dp) {
  for (int i = 17; i >= 0; i--)
    if (dp >= (1 << i)) u = f[u][i], dp -= (1 << i);
  return u;
}
signed main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs(1, 1);
  for (int i = 1; i <= q; i++) {
    int opt, v = 0, x = 0, d = 0;
    scanf("%d", &opt);
    if (opt == 0) {
      scanf("%d %d %d", &v, &x, &d);
      d = min(d, n);
      int d1 = dep[v] + d, d2 = dep[v] - d;
      if (d2 < 2) {
        int tmp1 = 2 - d2, tv = findSon(v, d), tu;
        Depth.insert(1, 1, n, 1, tmp1, x);
        if (tmp1 + 1 > dep[v])
          tu = findSon(v, tmp1 + 1 - dep[v]);
        else
          tu = findFa(v, dep[v] - tmp1 - 1);
        if (dep[tu] > tmp1) Chain.insert(1, 1, n, dfn[tu], dfn[tv], x);
      } else {
        int tu = findFa(v, d), tv = findSon(v, d);
        Chain.insert(1, 1, n, dfn[tu], dfn[tv], x);
      }
    } else {
      scanf("%d", &v);
      printf("%d\n",
             Depth.query(1, 1, n, dep[v]) + Chain.query(1, 1, n, dfn[v]));
    }
  }
  return 0;
}
