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.util.List;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Diego Huerfano ( diego.link )
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    private class BIT{
        private int tree[], n;
        BIT( int n ) {
            this.n=n;
            tree=new int[n+2];
        }

        public int read( int index ) {
            int acc=0;
            while( index>=1 ) {
                acc+=tree[index];
                index-=index&-index;
            }
            return acc;
        }

        public void add( int index, int val ) {
            while ( index<=n ) {
                tree[index]+=val;
                index+=index&-index;
            }
        }
    }

    private List<ArrayList<Integer>> tree=new ArrayList<ArrayList<Integer>>();
    private int depth[], chainID[];
    private boolean vst[];

    private int dfs( int u, int depth, int chain ) {
        vst[u]=true;
        this.depth[u]=depth;
        chainID[u]=chain;
        for( int v : tree.get( u ) ) {
            if( !vst[v] )
                return 1+dfs( v, depth+1, chain );
        }
        return 1;
    }

    public void solve(int testNumber, InputReader in, OutputWriter out) {
        final int n=in.readInt(), q=in.readInt();
        for( int i=0; i<n; i++ )
            tree.add( new ArrayList<Integer>() );
        for( int i=0; i<n-1; i++ ) {
            int u=in.readInt()-1, v=in.readInt()-1;
            tree.get( u ).add( v );
            tree.get( v ).add( u );
        }

        depth=new int[n];
        chainID=new int[n];
        vst=new boolean[n];
        int chainNum=0;
        vst[0]=true;
        List<Integer> size=new ArrayList<Integer>();
        for( int v : tree.get( 0 ) ) {
            if( !vst[v] )
                size.add( 1+dfs( v, 2, chainNum++ ) );
        }

        List<BIT> bits=new ArrayList<BIT>(chainNum);
        BIT rootBit=new BIT( n );
        for( int i=0; i<chainNum; i++ )
            bits.add( new BIT( size.get( i ) ) );

        for( int i=0; i<q; i++ ) {
            int kind=in.readInt();
            if( kind==0 ) {
                int v=in.readInt()-1, x=in.readInt(), d=in.readInt();
                if( v==0 ) {
                    rootBit.add( 1, x );
                    rootBit.add( d+2, -x );
                } else {
                    BIT curBit=bits.get( chainID[v] );
                    if( d<=depth[v]-2 ) {
                        curBit.add( depth[v]-d, x );
                        curBit.add( Math.min( depth[v]+d+1, size.get( chainID[v] )+1 ), -x );
                    } else {
                        rootBit.add( 1, x );
                        rootBit.add( d-depth[v]+3, -x );
                        int lo=d-depth[v]+3;
                        int hi=Math.min( d+depth[v]+1, size.get( chainID[v] )+1 );
                        curBit.add( lo, x );
                        curBit.add( hi, -x );
                    }
                }
            } else {
                int v=in.readInt()-1;
                if( v==0 )
                    out.printLine( rootBit.read( 1 ) );
                else
                    out.printLine( bits.get( chainID[v] ).read( depth[v] ) + rootBit.read( depth[v] ) );
            }
        }
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print( objects );
        writer.println();
    }

    public void close() {
        writer.close();
    }
}

