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 MOD = (long long)1e9 + 7;
const double PI = acos(-1.0);
void __print(long long x) { cerr << x; }
void __print(int32_t x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const long long N = 1e5 + 10;
vector<long long> adj[N];
void dfs(long long cur, long long par, vector<long long> &v) {
  v.push_back(cur);
  for (auto x : adj[cur]) {
    if (x != par) {
      dfs(x, cur, v);
    }
  }
}
long long p[N], dep[N];
vector<vector<long long>> bit;
long long root = 0;
void add(long long pos, long long line, long long val) {
  for (long long i = pos; i < (long long)bit[line].size(); i = i | (i + 1)) {
    bit[line][i] += val;
  }
}
long long get(long long pos, long long line) {
  long long ans = 0;
  for (long long i = pos; i >= 0; i = (i & (i + 1)) - 1) {
    ans += bit[line][i];
  }
  return ans;
}
void rangeUpdate(long long line, long long l, long long r, long long val) {
  add(l, line, val);
  add(r + 1, line, -val);
}
int32_t main() {
  long long n, q;
  cin >> n >> q;
  for (long long i = 0; i < n - 1; i++) {
    long long x, y;
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  vector<vector<long long>> a;
  for (auto x : adj[1]) {
    a.emplace_back();
    dfs(x, 1, a.back());
  }
  bit.resize(a.size() + 2);
  long long maxi = 0;
  for (long long i = 0; i < (long long)a.size(); i++) {
    for (long long j = 0; j < (long long)a[i].size(); j++) {
      p[a[i][j]] = i;
      dep[a[i][j]] = j;
    }
    bit[i].assign(a[i].size() + 1, 0);
    maxi = max(maxi, (long long)a[i].size());
  }
  bit[a.size()].assign(maxi + 2, 0);
  while (q--) {
    long long type;
    cin >> type;
    if (type == 0) {
      long long v, x, d;
      cin >> v >> x >> d;
      if (v == 1) {
        root += x;
        rangeUpdate((long long)a.size(), 0, d - 1, x);
      } else {
        if (dep[v] >= d) {
          rangeUpdate(p[v], dep[v] - d,
                      min(dep[v] + d, (long long)a[p[v]].size() - 1), x);
        } else {
          long long overflow = d - dep[v] - 1;
          root += x;
          long long l = 0, r = min((long long)a[p[v]].size() - 1, dep[v] + d);
          l = overflow;
          if (l <= r) {
            rangeUpdate(p[v], l, r, x);
          }
          if (overflow) {
            rangeUpdate((long long)a.size(), 0, overflow - 1, x);
          }
        }
      }
    } else {
      long long v;
      cin >> v;
      if (v == 1) {
        cout << root << '\n';
      } else {
        cout << get(dep[v], p[v]) + get(dep[v], (long long)a.size()) << '\n';
      }
    }
  }
  return 0;
}
