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;
int N, Q;
vector<vector<int> > M;
template <class T>
struct Fenwick {
  int n;
  vector<T> data;
  Fenwick(){};
  Fenwick(int n) : n(n) { data = vector<T>(n); }
  void add(int p, T v) {
    for (; p < n; p |= p + 1) data[p] += v;
  }
  T sum(int l, int r) {
    if (l == 0) {
      T t = 0;
      for (; r; r &= r - 1) t += data[r - 1];
      return t;
    } else {
      return sum(0, r) - sum(0, l);
    }
  }
};
int main() {
  scanf("%d%d", &N, &Q);
  M = vector<vector<int> >(N);
  for (int i = 1; i < N; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    M[a].push_back(b);
    M[b].push_back(a);
  }
  vector<int> depth(N, -1), group(N, -1), sz(M[0].size()), depth_count;
  queue<int> qu;
  qu.push(0);
  depth[0] = 0;
  for (int k = 1; !qu.empty(); k++) {
    int e = qu.front();
    qu.pop();
    if (int(depth_count.size()) <= depth[e])
      depth_count.push_back(1);
    else
      depth_count[depth[e]]++;
    for (int i = 0; i < int(M[e].size()); i++) {
      int f = M[e][i];
      if (depth[f] < 0) {
        depth[f] = depth[e] + 1;
        qu.push(f);
      }
    }
  }
  for (int i = 0; i < int(M[0].size()); i++) {
    for (int e = M[0][i];;) {
      sz[i]++;
      group[e] = i;
      if (M[e].size() == 1) break;
      e = (depth[M[e][0]] > depth[e] ? M[e][0] : M[e][1]);
    }
  }
  Fenwick<int> all(depth_count.size());
  vector<Fenwick<int> > p(M[0].size());
  for (int i = 0; i < int(M[0].size()); i++) {
    p[i] = Fenwick<int>(sz[i]);
  }
  for (; Q--;) {
    int t;
    scanf("%d", &t);
    if (t) {
      int v;
      scanf("%d", &v);
      v--;
      printf("%d\n", all.sum(0, depth[v] + 1) + p[group[v]].sum(0, depth[v]));
    } else {
      int v, x, d;
      scanf("%d%d%d", &v, &x, &d);
      v--;
      if (v == 0) {
        all.add(0, x);
        all.add(d + 1, -x);
      } else {
        if (d >= depth[v]) {
          int dd = d - depth[v];
          all.add(0, x);
          all.add(dd + 1, -x);
          p[group[v]].add(dd, x);
          p[group[v]].add(depth[v] + d, -x);
        } else {
          p[group[v]].add(depth[v] - d - 1, x);
          p[group[v]].add(depth[v] + d, -x);
        }
      }
    }
  }
  return 0;
}
