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.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Random;
import java.util.StringTokenizer;

/**
 * @author Polyarniy Nickolay
 */
public class ProblemE {

    private BufferedReader in;
    private PrintWriter out;
    private StringTokenizer tok;
    private final String DELIMETER = " ";
    private final boolean ENABLE_MULTITEST = false;
    private final boolean DEBUG = true;
    private final String FILENAME = null;//if FILENAME = null, then works with console

    public void run() throws Exception {
        initInputOutput();
        do {
            init();
            solve();
        } while (hasMoreTokens() && ENABLE_MULTITEST);
        finish();
    }
    int n;
    int q;
    ArrayList<Integer>[] ma;
    int[] treeNum;
    int[] indInTree;
    Tree[] trees;
    Tree commonTree;
    int valueInRoot;

    private void init() throws Exception {
        n = nextInt();
        q = nextInt();
        ma = new ArrayList[n];
        treeNum = new int[n];
        indInTree = new int[n];
        valueInRoot = 0;
    }

    private void solve() throws Exception {
        for (int i = 0; i < n; ++i) {
            ma[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n - 1; ++i) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            ma[u].add(v);
            ma[v].add(u);
        }
        {
            trees = new Tree[ma[0].size()];
            int curTree = 0;
            for (int i : ma[0]) {
                curTreeLen = 0;
                setNumOfTree(i, 0, curTree);
                trees[curTree] = new Tree(curTreeLen);
                curTree++;
            }
            commonTree = new Tree(n);
        }
        for (int i = 0; i < q; ++i) {
            int com = nextInt();
            if (com == 0) {
                int v = nextInt() - 1;
                int x = nextInt();
                int d = nextInt();
                if (v == 0) {
//                    out.println("Ading to root +" + x);
//                    out.flush();
                    valueInRoot += x;
//                    out.println("Adding to common: 0.." + (d - 1) + " +" + x);
//                    out.flush();
                    if (d >= 1) {
                        commonTree.add(0, d - 1, x);
                    }
                } else {
                    Tree tree = trees[treeNum[v]];
                    int indInTr = indInTree[v];
                    if (indInTr + 1 < d) {
                        int tmp = d - indInTr - 2;
                        if (Math.min(tree.size() - 1, indInTr + d) > tmp) {
//                            out.println("Adding to tree[" + treeNum[v] + "] " + (tmp + 1)
//                                    + ".." + Math.min(tree.size() - 1, indInTr + d) + " +" + x);
//                            out.flush();
                            tree.add(tmp + 1, Math.min(tree.size() - 1, indInTr + d), x);
                        }
                    } else {
//                        out.println("Adding to tree[" + treeNum[v] + "] " + (Math.max(0, indInTr - d))
//                                + ".." + (Math.min(tree.size() - 1, indInTr + d)) + " +" + x);
//                        out.flush();
                        tree.add(Math.max(0, indInTr - d), Math.min(tree.size() - 1, indInTr + d), x);
                    }
                    if (indInTr + 1 <= d) {
//                        out.println("Ading to root +" + x);
//                        out.flush();
                        valueInRoot += x;
                    }
                    if (indInTr + 1 < d) {
//                        out.println("Adding to common: 0.." + (d - indInTr - 2) + " +" + x);
//                        out.flush();
                        commonTree.add(0, d - indInTr - 2, x);
                    }
                }
            } else {
                int v = nextInt() - 1;
                if (v != 0) {
//                    out.println("Getting v[" + v + "]");
//                    out.flush();
                    out.println(trees[treeNum[v]].get(indInTree[v]) + commonTree.get(indInTree[v]));
//                    out.flush();
                } else {
//                    out.println("Getting root");
//                    out.flush();
                    out.println(valueInRoot);
//                    out.flush();
                }
            }
        }
    }
    int curTreeLen;

    private void setNumOfTree(int v, int prev, int treeNum) {
        indInTree[v] = curTreeLen;
        curTreeLen++;
        this.treeNum[v] = treeNum;
        for (int u : ma[v]) {
            if (u != prev) {
                setNumOfTree(u, v, treeNum);
            }
        }
    }

    class Tree {

        int size;
        int n;
        int[] t;

        public Tree(int n) {
            this.size = n;
            this.n = 1;
            while (this.n < n) {
                this.n *= 2;
            }
            t = new int[2 * this.n];
//            out.println("          N=" + n + "         len=" + (this.n));
//            out.flush();
        }

        private int size() {
            return this.size;
        }

        private void add(int l, int r, int x) {
//            out.println("_Add l=" + l + " r=" + r + " x=" + x);
//            out.flush();
            l = n + l;
            r = n + r;
            while (l <= r) {
//                out.println("____ l=" + l + " r=" + r);
//                out.flush();
                if (l % 2 == 1) {
                    t[l] += x;
                    l++;
                }
                if (r % 2 == 0) {
                    t[r] += x;
                    r--;
                }
                l /= 2;
                r /= 2;
            }
        }

        private int get(int ind) {
//            out.println(" Get "+ind+" n="+n);
//            out.flush();
            pushTo(1, ind + n, n, n + n - 1);
            return t[ind + n];
        }

        void pushTo(int cur, int v, int rl, int rr) {
//            out.println(" Push cur=" + cur + " v=" + v+" rl="+rl+" rr="+rr);
//            out.flush();
            if (v == cur) {
                return;
            } else {
                int rm = (rl + rr) / 2;
                pushDown(cur);
                if (rl <= v && v <= rm) {
                    pushTo(2 * cur, v, rl, rm);
                } else if (rm < v && v <= rr) {
                    pushTo(2 * cur + 1, v, rm + 1, rr);
                }
            }
        }

        void pushDown(int cur) {
            if (2 * cur < t.length) {
                t[2 * cur] += t[cur];
                t[2 * cur + 1] += t[cur];
            }
            if (cur < t.length) {
                t[cur] = 0;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        ProblemE solution = new ProblemE();
        solution.run();
    }

    private void initInputOutput() throws Exception {
        if (FILENAME == null) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    private void shuffleArray(Object[] arr) {
        Random r = new Random();
        for (int i = 0; i < arr.length; ++i) {
            Object tmp = arr[i];
            int j = r.nextInt(arr.length);
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

    private void shuffleArray(int[] arr) {
        Random r = new Random();
        for (int i = 0; i < arr.length; ++i) {
            int tmp = arr[i];
            int j = r.nextInt(arr.length);
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

    private int[] nextArrayInt(int n) throws Exception {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = nextInt();
        }
        return res;
    }

    private String nextWord() throws Exception {
        if (updateTokenizer()) {
            return null;
        } else {
            return tok.nextToken();
        }
    }

    private boolean hasMoreTokens() throws Exception {
        return !updateTokenizer();
    }

    private boolean updateTokenizer() throws Exception {
        while (tok == null || !tok.hasMoreTokens()) {
            String nextLine = in.readLine();
            if (nextLine == null || nextLine.isEmpty()) {
                return true;
            }
            tok = new StringTokenizer(nextLine, DELIMETER);
        }
        return false;
    }

    private int nextInt() throws Exception {
        return Integer.parseInt(nextWord());
    }

    private long nextLong() throws Exception {
        return Long.parseLong(nextWord());
    }

    private void finish() throws Exception {
        in.close();
        out.close();
    }

    private void print(String s) {
        if (DEBUG) {
            System.out.print(s);
        }
    }

    private void println(String s) {
        if (DEBUG) {
            System.out.println(s);
        }
    }

    private void println() {
        if (DEBUG) {
            System.out.println();
        }
    }

    private long[] getFirstSimpleNums(int n) {
        boolean[] notPr = new boolean[n];
        int res = n;
        notPr[0] = true;
        res--;
        notPr[1] = true;
        res--;
        for (int i = 2; i < n; ++i) {
            if (!notPr[i]) {
                for (int j = i + i; j < n; j += i) {
                    if (!notPr[j]) {
                        notPr[j] = true;
                        res--;
                    }
                }
            }
        }
        long[] resA = new long[res];
        int next = 0;
        for (int i = 0; i < n; i++) {
            if (!notPr[i]) {
                resA[next] = i;
                next++;
            }
        }
        return resA;
    }

    private static class Pair {

        int a;
        int b;

        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
        public static final Comparator<Pair> comparator = new Comparator<Pair>() {

            @Override
            public int compare(Pair pair1, Pair pair2) {
                return (pair1.a - pair2.a) != 0 ? (pair1.a - pair2.a) : (pair1.b - pair2.b);
            }
        };

        @Override
        public String toString() {
            return "{" + a + "|" + b + '}';
        }
    }
}
