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.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class A {
	static ArrayList<Integer> [] adj;
	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt(), q = sc.nextInt();
		adj = new ArrayList[n];
		for (int i = 0; i < adj.length; ++i) {
			adj[i] = new ArrayList<>();
		}
		for (int i = 0; i < n-1; ++i) {
			int u = sc.nextInt(), v = sc.nextInt();
			--u; --v;
			adj[u].add(v);
			adj[v].add(u);
		}
		num = 1;
		idx = new int[n];
		par = new int[n];
		realPar = new int[n];
		lev = new int[n];
		tout = new int[n];
		int [] idxLev = new int[n];
		int [] maxLev = new int[n];
		Arrays.fill(maxLev, n);
		dfs(0, -1, 0, 0);
		int N = 1; while(N < n) N <<= 1; //padding
		SegmentTree chains = new SegmentTree(N);
		SegmentTree levels = new SegmentTree(N);
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);
		num = 1;
		while(!queue.isEmpty()) {
			int u = queue.poll();
			idxLev[u] = num;
			maxLev[lev[u]] = num++;
			for(int v:adj[u])
				if(v != realPar[u]){
					queue.add(v);
				}
		}
		while(q-- > 0) {
			int type = sc.nextInt(), v = sc.nextInt()-1;
			if(type == 0) {
				int x = sc.nextInt(), d = sc.nextInt();
				int l = lev[v];
				int p = v == 0?0:par[v];
				if(d > l) {
					levels.update_range(1, maxLev[d-l], x);
					chains.update_range(idx[p] + d-l, Math.min(tout[p], idx[p] + d + l - 1), x);
				}
				else if(d == l) {
					chains.update_point(idx[0], x);
					chains.update_range(idx[p], Math.min(tout[p], idx[p] + d + l - 1), x);
				}
				else {
					chains.update_range(idx[p] + l - d - 1, Math.min(tout[p], idx[p] + l + d - 1), x);
				}
			}
			else { 
				out.println(levels.query(idxLev[v], idxLev[v]) + chains.query(idx[v], idx[v]));
			}
//			for (int i = 0; i < n; ++i) {
//				System.out.println(levels.query(idxLev[i], idxLev[i]) + chains.query(idx[i], idx[i]));
//			}
//			System.out.println();
		}
		out.close();
	}
	static int num;
	static int [] idx, par, realPar, lev, tout;
	static void dfs(int u, int realp, int p, int l) {
		par[u] = p;
		idx[u] = num++;
		lev[u] = l;
		realPar[u] = realp;
		for(int v:adj[u])
			if(v != realp)
				dfs(v, u, p == 0?v:p, l+1);
		tout[u] = num-1;
	}
	static class SegmentTree {		// 1-based DS, OOP
		
		int N; 			//the number of elements in the array as a power of 2 (i.e. after padding)
		int[] lazy;
		long [] sTree;
		
		SegmentTree(int n)		
		{
			N = n;
			sTree = new long[N<<1];		//no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new int[N<<1];
		}
		
		void update_point(int index, int val)			// O(log n)
		{
			index += N - 1;				
			sTree[index] += val;			
			while(index>1)				
			{
				index >>= 1;
				sTree[index] = sTree[index<<1] + sTree[index<<1|1];		
			}
		}
		
		
		void update_range(int i, int j, int val)		// O(log n) 
		{
			update_range(1,1,N,i,j,val);
		}
		
		void update_range(int node, int b, int e, int i, int j, int val)
		{
			if(i > e || j < b)		
				return;
			if(b >= i && e <= j)		
			{
				sTree[node] += 1l*(e-b+1)*val;			
				lazy[node] += val;				
			}							
			else		
			{
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node<<1,b,mid,i,j,val);
				update_range(node<<1|1,mid+1,e,i,j,val);
				sTree[node] = sTree[node<<1] + sTree[node<<1|1];		
			}
			
		}
		void propagate(int node, int b, int mid, int e)		
		{
			lazy[node<<1] += lazy[node];
			lazy[node<<1|1] += lazy[node];
			sTree[node<<1] += 1l*(mid-b+1)*lazy[node];		
			sTree[node<<1|1] += 1l*(e-mid)*lazy[node];		
			lazy[node] = 0;
		}
		
		long query(int i, int j)
		{
			return query(1,1,N,i,j);
		}
		
		long query(int node, int b, int e, int i, int j)	// O(log n)
		{
			if(i>e || j <b)
				return 0;		
			if(b>= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			propagate(node, b, mid, e);
			long q1 = query(node<<1,b,mid,i,j);
			long q2 = query(node<<1|1,mid+1,e,i,j);
			return q1 + q2;	
					
		}
	}
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}
	}

}