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*.
The first line contains integers *n* (2 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) and *q* (1 ≤ *q* ≤ 10<sup class="upper-index">5</sup>) — the number of tree nodes and the number of requests, correspondingly.

Each of the next *n*  -  1 lines contains two integers *u*<sub class="lower-index">*i*</sub> and *v*<sub class="lower-index">*i*</sub> (1 ≤ *u*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub> ≤ *n*, *u*<sub class="lower-index">*i*</sub> ≠ *v*<sub class="lower-index">*i*</sub>), that show that there is an edge between nodes *u*<sub class="lower-index">*i*</sub> and *v*<sub class="lower-index">*i*</sub>. 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* ≤ 10<sup class="upper-index">4</sup>, 1 ≤ *d* &lt; *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.
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
int inTree[100100];
int depth[100100];
vector<vector<int>> t;

void dfs(int v, int d, int num, int p) {
  inTree[v] = num;
  depth[v] = d;
  t[num].push_back(0);

  for (int i = 0; i < g[v].size(); i++) {
    if (g[v][i] == p) continue;
    dfs(g[v][i], d + 1, num, v);
  }
}

void add(int p, int v, int num) {
  for (int i = p; i < t[num].size(); i += (i & (-i))) t[num][i] += v;
}

int find(int p, int num) {
  int res = 0;
  for (int i = p; i > 0; i -= (i & (-i))) res += t[num][i];
  return res;
}

int main() {
  int n, q;
  cin >> n >> q;
  g.resize(n);

  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }

  t.resize(g[0].size() + 1);

  int inRoot = 0;

  for (int i = 0; i < g[0].size(); i++) {
    t[i].push_back(0);
    dfs(g[0][i], 1, i, 0);
  }

  t[t.size() - 1].resize(n + 10);
  for (int i = 0; i < q; i++) {
    int ty;
    scanf("%d", &ty);
    if (ty == 0) {
      int v, val, dist;
      scanf("%d%d%d", &v, &val, &dist);
      v--;
      if (v == 0) {
        inRoot += val;
        add(1, val, t.size() - 1);
        add(dist + 1, -val, t.size() - 1);
      } else {
        if (dist >= depth[v]) {
          int left = dist - depth[v];
          inRoot += val;
          add(1, val, t.size() - 1);
          add(left + 1, -val, t.size() - 1);
          add(left + 1, val, inTree[v]);
          add(depth[v] + dist + 1, -val, inTree[v]);
        } else {
          add(depth[v] - dist, val, inTree[v]);
          add(depth[v] + dist + 1, -val, inTree[v]);
        }
      }
    } else {
      int v;
      scanf("%d", &v);
      v--;
      if (v == 0)
        printf("%d\n", inRoot);
      else {
        int res = find(depth[v], inTree[v]) + find(depth[v], t.size() - 1);
        printf("%d\n", res);
      }
    }
  }

  return 0;
}
				  	 	 						 	  			 		 				