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;
inline long long Min(long long x, long long y) { return x < y ? x : y; }
inline void read(long long &x) {
  x = 0;
  long long f = 1;
  char s = getchar();
  while (s < '0' || s > '9') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while (s >= '0' && s <= '9') {
    x = (x << 3) + (x << 1) + (s ^ 48);
    s = getchar();
  }
  x *= f;
}
vector<long long> G[100005];
long long Dep[100005], Dfn[100005], Cnt;
struct node {
  struct SegMentTree {
    long long Val, Lazy;
  } Tree[100005 << 2];
  inline void PushDown(long long x) {
    if (!Tree[x].Lazy) return;
    Tree[x << 1].Val += Tree[x].Lazy;
    Tree[x << 1 | 1].Val += Tree[x].Lazy;
    Tree[x << 1].Lazy += Tree[x].Lazy;
    Tree[x << 1 | 1].Lazy += Tree[x].Lazy;
    Tree[x].Lazy = 0;
  }
  void Modify(long long x, long long l, long long r, long long Ql, long long Qr,
              long long w) {
    if (Ql > Qr) return;
    if (l == r) {
      Tree[x].Val += w;
      return;
    }
    if (Ql <= l && r <= Qr) {
      Tree[x].Val += w;
      Tree[x].Lazy += w;
      return;
    }
    PushDown(x);
    long long Mid = (l + r) / 2;
    if (Qr <= Mid)
      Modify(x << 1, l, Mid, Ql, Qr, w);
    else if (Ql > Mid)
      Modify(x << 1 | 1, Mid + 1, r, Ql, Qr, w);
    else
      Modify(x << 1, l, Mid, Ql, Mid, w),
          Modify(x << 1 | 1, Mid + 1, r, Mid + 1, Qr, w);
    Tree[x].Val = Tree[x << 1].Val + Tree[x << 1 | 1].Val;
  }
  long long Query(long long x, long long l, long long r, long long Ql,
                  long long Qr) {
    if (l == r) return Tree[x].Val;
    if (Ql <= l && r <= Qr) return Tree[x].Val;
    PushDown(x);
    long long Mid = (l + r) / 2;
    if (Qr <= Mid)
      return Query(x << 1, l, Mid, Ql, Qr);
    else if (Ql > Mid)
      return Query(x << 1 | 1, Mid + 1, r, Ql, Qr);
    else
      return Query(x << 1, l, Mid, Ql, Mid) +
             Query(x << 1 | 1, Mid + 1, r, Mid + 1, Qr);
  }
} Chain, Depth;
long long Root = 1, Lian[100005], End[100005], Begin[100005], Du[100005],
          totLian;
void Dfs(long long x, long long Pre) {
  Dfn[x] = ++Cnt;
  int l = G[x].size();
  bool Leaf = 1;
  for (register int i = 0; i < l; ++i) {
    long long to = G[x][i];
    if (to == Pre) continue;
    Leaf = 0;
    Dep[to] = Dep[x] + 1;
    if (x == Root)
      Lian[to] = ++totLian, Begin[Lian[to]] = to;
    else
      Lian[to] = Lian[x];
    Dfs(to, x);
  }
  if (Leaf) End[Lian[x]] = x;
}
int main() {
  long long n, q;
  read(n);
  read(q);
  for (register int i = 1; i < n; ++i) {
    long long u, v;
    read(u);
    read(v);
    G[u].push_back(v);
    G[v].push_back(u);
    if (++Du[u] > 2) Root = u;
    if (++Du[v] > 2) Root = v;
  }
  Dep[Root] = 1;
  Dfs(Root, Root);
  while (q--) {
    long long Type;
    read(Type);
    if (Type == 0) {
      long long u, d, x;
      read(u);
      read(x);
      read(d);
      if (Dep[u] - d > 1)
        Chain.Modify(1, 1, n, Dfn[u] - d, Dfn[u], x);
      else {
        Chain.Modify(1, 1, n, Dfn[Begin[Lian[u]]], Dfn[u], x);
        Depth.Modify(1, 1, n, 1, d - Dep[u] + 2, x);
        Chain.Modify(1, 1, n, Dfn[Begin[Lian[u]]],
                     Min(Dfn[Begin[Lian[u]]] + d - Dep[u], Dfn[End[Lian[u]]]),
                     -x);
      }
      Chain.Modify(1, 1, n, Dfn[u] + 1, Min(Dfn[End[Lian[u]]], Dfn[u] + d), x);
    } else {
      long long u;
      read(u);
      long long Quan = Depth.Query(1, 1, n, Dep[u], Dep[u]);
      long long Lian = Chain.Query(1, 1, n, Dfn[u], Dfn[u]);
      printf("%lld\n", Quan + Lian);
    }
  }
  return 0;
}
