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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author emotionalBlind
 */
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 {
    static class Node {
        int id;
        List<Node> adj = new ArrayList<Node>(0);
        int depth;
        int chain_id;
        }

    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int q = in.readInt();
        Node[] nodes = new Node[n];
        for (int i = 0; i < nodes.length; ++i) {
            nodes[i] = new Node();
            nodes[i].id = i;
        }

        for (int i = 0; i < n - 1; ++i) {
            int a = in.readInt() - 1;
            int b = in.readInt() - 1;
            nodes[a].adj.add(nodes[b]);
            nodes[b].adj.add(nodes[a]);
        }

        FenwickTree[] tree = new FenwickTree[nodes[0].adj.size()];
        for (int c = 0; c < nodes[0].adj.size(); ++c) {
            int len = dfs(nodes[0].adj.get(c), nodes[0], 1, c);
            tree[c] = new FenwickTree(len);
        }
        nodes[0].depth = 0;
        nodes[0].chain_id = -1;
        FenwickTree dtree = new FenwickTree(n);
        while (q-- > 0) {
            int type = in.readInt();
            if (type == 0) {
                int v = in.readInt() - 1;
                int x = in.readInt();
                int d = in.readInt();

                Node u = nodes[v];
                if (v == 0) {
                    dtree.updateRange(0, d, x);
                } else if (d >= u.depth) {
                    int d1 = d - u.depth;
                    dtree.updateRange(0, d1, x);
                    tree[u.chain_id].updateRange(d1 + 1, u.depth + d, x);
                } else {
                    tree[u.chain_id].updateRange(u.depth - d, u.depth + d, x);
                }
            } else {
                int v = in.readInt() - 1;
                int dep = nodes[v].depth;
                long res = dtree.read(dep);
                if (nodes[v].chain_id >= 0) {
                    res += tree[nodes[v].chain_id].read(nodes[v].depth);
                }
                out.printLine(res);
            }
        }
    }

    int dfs(Node u, Node parent, int depth, int chain) {
        u.depth = depth;
        u.chain_id = chain;
        for (Node v : u.adj) {
            if (v != parent) {
                return dfs(v, u, depth + 1, chain);
            }
        }
        return depth;
    }
}

class InputReader {

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

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

    public int read() {
        // InputMismatchException -> UnknownError
        if (numChars == -1)
            throw new UnknownError();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new UnknownError();
            }
            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();
        } else if (c == '+') {
            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 static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    }

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(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();
    }

}

class FenwickTree {
    long[] f;
    int size;
    boolean hasMod;
    long MOD;

    public FenwickTree(int size) {
        this.size = size + 1;
        f = new long[this.size + 1];
        hasMod = false;
    }

    public FenwickTree(int size, int mod) {
        this.MOD = mod;
        hasMod = true;
        this.size = size + 1;
        f = new long[this.size + 1];
    }

    public void update(int index, long val) {
        if (index >= size) return;
        index++;
        if (hasMod && val >= MOD) {
            val %= MOD;
        }

        while (index <= size) {
            f[index] = f[index] + val;
            if (hasMod) {
                if (f[index] >= MOD) {
                    f[index] -= MOD;
                } else if (f[index] < MOD) {
                    f[index] += MOD;
                }
            }
            index += (index & -index);
        }
    }

    public long read(int index) {
        if (index >= size) return 0;
        index++;
        long sum = 0;
        while (index > 0) {
            sum = sum + f[index];
            if (hasMod && sum >= MOD) {
                sum -= MOD;
            }
            index -= (index & -index);
        }
        return sum;
    }

    public void updateRange(int index1, int index2, long val) {
        update(index1, val);
        update(index2 + 1, -val);
    }
}

