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;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &x) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), x = 0; c >= '0' && c <= '9';
       c = getchar())
    x = (x << 1) + (x << 3) + c - '0';
  if (sg) x = -x;
}
template <class T>
inline void print(T x) {
  if (x < 0) {
    putchar('-');
    return print(-x);
  }
  if (x < 10) {
    putchar('0' + x);
    return;
  }
  print(x / 10);
  putchar(x % 10 + '0');
}
template <class T, class T1>
inline void gn(T &x, T1 &y) {
  gn(x);
  gn(y);
}
template <class T, class T1, class T2>
inline void gn(T &x, T1 &y, T2 &z) {
  gn(x);
  gn(y);
  gn(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
vector<int> adj[100111];
int deep[100111];
int id[100111];
int runs;
vector<int> bit[100111];
void dfs(int u, int fa) {
  id[u] = runs;
  bit[runs].push_back(0);
  deep[u] = deep[fa] + 1;
  for (int i = 0; i < ((int)adj[u].size()); i++) {
    int v = adj[u][i];
    if (v == fa) continue;
    dfs(v, u);
  }
}
struct BIT {
  void update(int now, int u, int x) {
    while (u <= ((int)bit[now].size()) - 1) {
      bit[now][u] += x;
      u += u & -u;
    }
  }
  int calc(int now, int u) {
    int ans = 0;
    smin(u, ((int)bit[now].size()) - 1);
    while (u) {
      ans += bit[now][u];
      u -= u & -u;
    }
    return ans;
  }
  void add(int now, int st, int ed, int x) {
    update(now, st, x);
    update(now, ed + 1, -x);
  }
} BIT;
void update(int v, int x, int d) {
  if (v == 1) {
    BIT.add(0, 1, 1 + d, x);
    return;
  }
  int now = id[v];
  int st = max(1, deep[v] - d);
  int ed = min(((int)bit[now].size()) - 1, deep[v] + d);
  BIT.add(now, st, ed, x);
  if (deep[v] <= d) {
    BIT.add(0, 1, d - deep[v] + 1, x);
    if (deep[v] < d) BIT.add(now, 1, d - deep[v], -x);
  }
}
int solve(int v) {
  int now = id[v];
  if (v == 1) {
    return BIT.calc(0, 1);
  }
  int ans = BIT.calc(now, deep[v]);
  ans += BIT.calc(0, deep[v] + 1);
  return ans;
}
int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    gn(u, v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  id[1] = runs;
  for (int i = 0; i < n + 1; i++) bit[0].push_back(0);
  for (int i = 0; i < ((int)adj[1].size()); i++) {
    int u = adj[1][i];
    runs++;
    bit[runs].push_back(0);
    dfs(u, 1);
  }
  int t, v, x, d;
  while (q--) {
    gn(t);
    if (t) {
      gn(v);
      printf("%d\n", solve(v));
    } else {
      gn(v, x, d);
      update(v, x, d);
    }
  }
  return 0;
}
