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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Solver {

	public static void main(String[] Args) throws NumberFormatException,
			IOException {
		new Solver().Run();
	}

	PrintWriter pw;
	StringTokenizer Stok;
	BufferedReader br;

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

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

	public double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}

	public long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}
	
	class Vertex{
		int remote;
		int parent;
		int numBranch;
		
		public Vertex(){
			remote=0;
			parent=-1;
			numBranch=0;
		}
	}

	final int MAX_RAD=100000;
	int n;
	int kolQuery;
	List<List<Integer>> edges;
	int[] lenBranches;
	int[][] fenwick;
	int[] sumBranch;
	Vertex[] verts;
	
	void goDFS(int numVertex, int parent, int depth, int numBranch){
		verts[numVertex].parent=parent;
		verts[numVertex].remote=depth;
		verts[numVertex].numBranch=numBranch;
		lenBranches[numBranch]++;
		for (int next : edges.get(numVertex)){
			if (next!=parent){
				goDFS(next,numVertex,depth+1,numBranch);
			}
		}
	}
	
	void reading() throws NumberFormatException, IOException{
		n=nextInt();
		kolQuery=nextInt();
		verts=new Vertex[n];
		int zn1, zn2;
		edges=new ArrayList<List<Integer>>();
		for (int i=0; i<n; i++){
			edges.add(new ArrayList<Integer>());
			verts[i]=new Vertex();
		}
		
		for (int i=0; i<n-1; i++){
			zn1=nextInt()-1;
			zn2=nextInt()-1;
			edges.get(zn1).add(zn2);
			edges.get(zn2).add(zn1);
		}
		
		int len=edges.get(0).size();
		lenBranches=new int[len+1];
		sumBranch=new int[len+1];
		fenwick=new int[len+1][];
		for (int i=0; i<len; i++){
			goDFS(edges.get(0).get(i),0,1,i+1);
		}
		
		for (int i=1; i<=len; i++){
			fenwick[i]=new int[lenBranches[i]+1];
		}
		lenBranches[0]=MAX_RAD;
		fenwick[0]=new int[MAX_RAD+2];
	}
	
	void addToFenwick(int[] fen, int numBranch, int index, int value){
		sumBranch[numBranch]+=value;
		while (index<= lenBranches[numBranch]){
			fen[index]+=value;
			index+=(index & -index);
		}
	}
	
	long getFromFenwick(int[] fen, int numBranch, int index){
		long result=0;
		index--;
		while (index>0){
			result+=fen[index];
			index-=(index & -index);
		}
		return sumBranch[numBranch]-result;
	}
	
	public void Run() throws NumberFormatException, IOException {
		//br = new BufferedReader(new FileReader("input.txt")); pw = new PrintWriter("output.txt");
		br=new BufferedReader(new InputStreamReader(System.in));  pw=new PrintWriter(new OutputStreamWriter(System.out));
		
		reading();
		
		for (int i=0; i<kolQuery; i++){
			int zn1;
			int numVert;
			int value;
			int dist;
			zn1=nextInt();
			if (zn1==0){
				numVert=nextInt()-1;
				value=nextInt();
				dist=nextInt();
				int farDist=Math.min(verts[numVert].remote+dist,lenBranches[verts[numVert].numBranch]);
				if (numVert>0)
					addToFenwick(fenwick[verts[numVert].numBranch], verts[numVert].numBranch, farDist, value);
				int nearDist=verts[numVert].remote-dist;
				if (nearDist>0 && numVert>0)
				{
					if (nearDist>1)
						addToFenwick(fenwick[verts[numVert].numBranch], verts[numVert].numBranch, nearDist-1, -value);
				}
				else{
					nearDist=-nearDist;
					addToFenwick(fenwick[0], 0, nearDist+1, value);
					nearDist=Math.min(nearDist, lenBranches[verts[numVert].numBranch]);
					if (numVert>0 && nearDist>0)
						addToFenwick(fenwick[verts[numVert].numBranch], verts[numVert].numBranch, nearDist, -value);
				}
			}
			else {
				numVert=nextInt()-1;
				if (numVert==0){
					pw.println(getFromFenwick(fenwick[0], 0, 1));
				}
				else
				{
					pw.println(getFromFenwick(fenwick[0],0,verts[numVert].remote+1)+getFromFenwick(fenwick[verts[numVert].numBranch], verts[numVert].numBranch, verts[numVert].remote));
				}
			}
		}
		pw.flush();
		pw.close();
	}

}
