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 long long maxn = 1e5 + 10;
vector<long long> V[maxn];
long long in[maxn], de[maxn], son[maxn];
long long tot, n, q;
void dfs(long long u, long long fa, long long dept) {
  in[u] = ++tot;
  de[u] = dept;
  son[u] = 0;
  for (long long i = 0; i < V[u].size(); i++) {
    long long v = V[u][i];
    if (v == fa) continue;
    dfs(v, u, dept + 1);
    son[u] = son[v] + 1;
  }
}
struct seg {
  long long tree[maxn << 2];
  long long add[maxn << 2];
  void pushup(long long rt) { tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; }
  void pushdown(long long L, long long R, long long rt) {
    if (add[rt] == 0) return;
    long long m = (L + R) >> 1;
    add[rt << 1] += add[rt];
    add[rt << 1 | 1] += add[rt];
    tree[rt << 1] += add[rt] * (m - L + 1);
    tree[rt << 1 | 1] += add[rt] * (R - m);
    add[rt] = 0;
  }
  void build(long long l, long long r, long long rt) {
    tree[rt] = add[rt] = 0;
    if (l == r) return;
    long long m = (r + l) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
  }
  void update(long long L, long long R, long long val, long long l, long long r,
              long long rt) {
    if (L <= l && R >= r) {
      tree[rt] += val * (r - l + 1);
      add[rt] += val;
      return;
    }
    pushdown(l, r, rt);
    long long m = (r + l) >> 1;
    if (L <= m) update(L, R, val, l, m, rt << 1);
    if (R > m) update(L, R, val, m + 1, r, rt << 1 | 1);
    pushup(rt);
  }
  long long query(long long pos, long long l, long long r, long long rt) {
    if (l == r) return tree[rt];
    pushdown(l, r, rt);
    long long m = (r + l) >> 1;
    if (pos <= m)
      return query(pos, l, m, rt << 1);
    else
      return query(pos, m + 1, r, rt << 1 | 1);
  }
  void print(long long l, long long r, long long rt) {
    if (l == r) return;
    pushdown(l, r, rt);
    long long m = (l + r) >> 1;
    print(l, m, rt << 1);
    print(m + 1, r, rt << 1 | 1);
  }
} Leve, List;
void update(long long v, long long x, long long d) {
  if (v == 1) {
    Leve.update(1, d + 1, x, 1, n, 1);
    return;
  }
  if (de[v] >= d) {
    long long L = in[v] - d;
    long long R = (son[v] < d) ? (in[v] + son[v]) : (in[v] + d);
    if (de[v] == d) {
      List.update(1, 1, x, 1, n, 1);
      List.update(L + 1, R, x, 1, n, 1);
    } else
      List.update(L, R, x, 1, n, 1);
  } else {
    long long len = d - de[v];
    Leve.update(1, len + 1, x, 1, n, 1);
    long long L = in[v] - (de[v] - len) + 1;
    long long R = (son[v] < d) ? (in[v] + son[v]) : (in[v] + d);
    List.update(L, R, x, 1, n, 1);
  }
}
long long query(long long v) {
  return Leve.query(de[v] + 1, 1, n, 1) + List.query(in[v], 1, n, 1);
}
signed main() {
  tot = 0;
  scanf("%lld%lld", &n, &q);
  Leve.build(1, n, 1);
  List.build(1, n, 1);
  for (long long i = 1; i <= n; i++) V[i].clear();
  for (long long i = 0; i < n - 1; i++) {
    long long a, b;
    scanf("%lld%lld", &a, &b);
    V[a].push_back(b);
    V[b].push_back(a);
  }
  dfs(1, -1, 0);
  long long op;
  while (q--) {
    scanf("%lld", &op);
    if (op == 0) {
      long long v, x, d;
      scanf("%lld%lld%lld", &v, &x, &d);
      update(v, x, d);
    } else if (op == 1) {
      long long v;
      scanf("%lld", &v);
      printf("%lld\n", query(v));
    }
  }
}
