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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.concurrent.ArrayBlockingQueue;

public class ProblemE {

	static class BITRange {
		BIT bit0;
		BIT bit1;
		BITRange(int n) {
			bit0 = new BIT(n);
			bit1 = new BIT(n);
		}
		
		void addRange(int l, int r, long x) {
			if (l > r) {
				return;
			}
			bit0.add(l, -x * (l-1));
			bit1.add(l, x);
			bit0.add(r+1, x * r);
			bit1.add(r+1, -x);
		}
		
		long range(int l, int r) {
			if (l > r) {
				return 0;
			}
			long right = bit0.sum(r) + bit1.sum(r) * r;
			long left = bit0.sum(l-1) + bit1.sum(l-1) * (l-1);
			return right - left;
		}
		
		long get(int i) {
			return range(i, i);
		}
	}

	static class BIT {
		long N;
		long[] data;

		BIT(int n) {
			N = n;
			data = new long[n + 1];
		}

		long sum(int i) {
			long s = 0;
			while (i > 0) {
				s += data[i];
				i -= i & (-i);
			}
			return s;
		}

		long range(int i, int j) {
			return sum(j) - sum(i - 1);
		}

		void add(int i, long x) {
			while (i <= N) {
				data[i] += x;
				i += i & (-i);
			}
		}
	}

	static int N;
	static List<Integer>[] graph;

	// グラフをBFSで辿る
	static int[] _bfsIndex;
	static int[] _depth;
	static List<Integer> _bfsDepthIndexes;

	static void bfs(int root) {
		int n = graph.length;
		_bfsIndex = new int[n];
		_depth = new int[n];
		_bfsDepthIndexes = new ArrayList<Integer>();
		Arrays.fill(_depth, -1);
		List<Integer> q = new ArrayList<Integer>(n + 1);
		q.add(root);
		_depth[root] = 0;

		int idx = 0;
		while (true) {
			List<Integer> nq = new ArrayList<Integer>();
			for (int now : q) {
				_bfsIndex[now] = idx++;
				int nowDepth = _depth[now];
				for (int next : graph[now]) {
					if (_depth[next] == -1) {
						_depth[next] = nowDepth + 1;
						nq.add(next);
					}
				}
			}
			_bfsDepthIndexes.add(idx);
			if (nq.size() == 0) {
				break;
			}
			q = nq;
		}
	}

	// グラフをDFSで辿る
	static int _dfsIdx;
	static int[] _dfsIndex;
	static int[] _dfsParent;
	static int[] _dfsLastChild;
	static List<Integer> _dfsDepthIndexes;

	static void dfs(int root) {
		int n = graph.length;
		_dfsIndex = new int[n];
		_dfsParent = new int[n];
		_dfsLastChild = new int[n];
		_dfsDepthIndexes = new ArrayList<Integer>();
		dfs(root, -1);
	}

	static void dfs(int now, int parent) {
		_dfsParent[now] = parent;
		_dfsIndex[now] = _dfsIdx++;
		boolean hasChild = false;
		for (int next : graph[now]) {
			if (next != parent) {
				hasChild = true;
				dfs(next, now);
			}
		}
		if (!hasChild) {
			_dfsDepthIndexes.add(_dfsIdx);
		}
		_dfsLastChild[now] = _dfsDepthIndexes.get(_dfsDepthIndexes.size()-1);
	}

	public static void main(String[] args) throws IOException {
		PrintWriter out = new PrintWriter(System.out);
		int n = nextInt();
		int q = nextInt();
		N = n;
		graph = new List[n];
		for (int i = 0; i < n; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < n - 1; i++) {
			int a = nextInt() - 1;
			int b = nextInt() - 1;
			graph[a].add(b);
			graph[b].add(a);
		}
		bfs(0);
		dfs(0);

		BITRange bfsBit = new BITRange(n+10);
		BITRange dfsBit = new BITRange(n+10);
		
		for (int i = 0; i < q; i++) {
			int type = nextInt();
			if (type == 0) {
				int v = nextInt() - 1;
				int x = nextInt();
				int d = nextInt();
				if (v == 0) {
					int bfs = Math.min(d, _bfsDepthIndexes.size()-1);
					bfsBit.addRange(1, _bfsDepthIndexes.get(bfs), x);
				} else if (_depth[v] <= d) {
					int bfs = Math.min(d - _depth[v], _bfsDepthIndexes.size()-1);
					int dfsFrom = (_dfsIndex[v] - _depth[v]) + (d - _depth[v]) + 1;
					int dfsTo = Math.min(_dfsIndex[v] + d, _dfsLastChild[v] - 1);
					bfsBit.addRange(1, _bfsDepthIndexes.get(bfs), x);
					dfsBit.addRange(dfsFrom+1, dfsTo+1, x);
				} else {
					int dfsFrom = _dfsIndex[v] - d;
					int dfsTo = Math.min(_dfsIndex[v] + d, _dfsLastChild[v] - 1);
					dfsBit.addRange(dfsFrom+1, dfsTo+1, x);
				}
			} else {
				int v = nextInt()-1;
				out.println(bfsBit.get(_bfsIndex[v]+1) + dfsBit.get(_dfsIndex[v]+1));
			}
		}
		out.flush();
	}

	static BufferedReader s = new BufferedReader(new InputStreamReader(
			System.in));
	static StringTokenizer st;

	static String nextString() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(s.readLine());
		}
		return st.nextToken();
	}

	static int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextString());
	}

	public static void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}