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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;

@SuppressWarnings("unchecked")
public class E276 {
	
	int n, q;
	ArrayList<Integer>[] vs;
	
	int[] pre, chain; int idx = 1, chains;
	int[] first, last; //for each chain
	void dfs(int node, int par, int c) { 
		chain[node] = c; 
		pre[node] = idx++;
		last[c] = node;
		for(int v : vs[node]) if(v != par) dfs(v, node, c);
	}
	
	SuperBIT root, bit;
	
	public void solve(JoltyScanner in, PrintWriter out) {
		n = in.nextInt(); q = in.nextInt();
		vs = new ArrayList[n];
		pre = new int[n];
		chain = new int[n];
		first = new int[n];
		last = new int[n];
		root = new SuperBIT(n);
		bit = new SuperBIT(n);
		for(int i = 0; i < n; ++i) vs[i] = new ArrayList<>();
		for(int i = 0; i < n - 1; ++i) {
			int u = in.nextInt() - 1, v = in.nextInt() - 1;
			vs[u].add(v); vs[v].add(u);
		}
		for(int i : vs[0]) {
			first[chains] = i;
			dfs(i, 0, chains++);
		}
		while(q-->0) {
			int type = in.nextInt();
			int node = in.nextInt() - 1;
			int me = pre[node];
			int myChain = chain[node];
			int firstInChain = first[myChain], lastInChain = last[myChain];
			int distToRoot = 1 + me - pre[firstInChain];
			if(type == 1) {
				long ans = bit.query(me, me) + root.query(distToRoot, distToRoot);
				out.println(ans);
			} else {
				
				long x = in.nextLong();
				int dist = in.nextInt();
				
				//first handle the root
				if(node == 0) {
					root.update(0, dist, x);
					continue;
				}
				
				//handle going down
				int last = Math.min(me + dist, pre[lastInChain]);
				if(me < last) bit.update(me + 1, last, x);
				
				//handle going up
				int first = me - dist;
				if(first >= pre[firstInChain]) { //easy case, doesn't hit root
					bit.update(first, me, x);
				} else { //hits root
					bit.update(pre[firstInChain], me, x); //first update to top of 
					int distRem = dist - distToRoot;
					//now update all things this far away from root
					root.update(0, distRem, x);
					//we updated stuff in this chain, so we should kill stuff that got updated from the root
					int firstRem = distRem - 1; //distance remaining from the first thing in the first node in this chain
					if(firstRem < 0) continue;
					
					last = pre[firstInChain] + firstRem;
					last = Math.min(pre[lastInChain], last);
					
					bit.update(pre[firstInChain], last, -x);
				}
			}
		}
	}
	
	static class SuperBIT {
		long[] dataMul, dataAdd;

		SuperBIT(int n) {
			n += 10;
			dataMul = new long[n];
			dataAdd = new long[n];
		}

		void update(int left, int right, long val) {
			left += 5; right += 5;
			internalUpdate(left, val, -val * (left - 1));
			internalUpdate(right, -val, val * right);
		}

		void internalUpdate(int at, long mul, long add) {
			while (at < dataMul.length) {
				dataMul[at] += mul;
				dataAdd[at] += add;
				at |= (at + 1);
			}
		}

		long query(int at) {
			long mul = 0;
			long add = 0;
			int start = at;
			while (at >= 0) {
				mul += dataMul[at];
				add += dataAdd[at];
				at = (at & (at + 1)) - 1;
			}
			return mul * start + add;
		}

		long query(int left, int right) {
			left += 5; right += 5;
			if (left > right) {
				int temp = left;
				left = right;
				right = temp;
			}
			return query(right) - query(left - 1);
		}
	}
	
	public static void main(String[] args) {
		JoltyScanner in = new JoltyScanner();
		PrintWriter out = new PrintWriter(System.out);
		new E276().solve(in, out);
		out.close();
	}
	static class JoltyScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public JoltyScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public JoltyScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
	        while(c!='.'&&c!='-'&&(c <'0' || c>'9')) c = nextChar();
	        boolean neg = c=='-';
	        if(neg)c=nextChar();
	        boolean fl = c=='.';
	        double cur = nextLong();
	        if(fl) return neg ? -cur/num : cur/num;
	        if(c == '.') {
	            double next = nextLong();
	            return neg ? -cur-next/num : cur+next/num;
	        }
	        else return neg ? -cur : cur;
	    }

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}

}
