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.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        new Main().run(in, out);
        out.close();
    }

    public static long mod = 17352642619633L;


    int N, M;
    List<Integer>[] adj;
    void run(FastScanner in, PrintWriter out) {
        // binary jumping + preorder/postorder nums + segment tree
        // binary jumping can be replaced by a list

        N = in.nextInt();
        M = in.nextInt();
        adj = new List[N+1];
        for (int i = 0; i < adj.length; i++) adj[i] = new ArrayList<>();

        for (int i = 0; i < N-1; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            adj[u].add(v);
            adj[v].add(u);
        }

        int bid = 0;
        for (int v : adj[1]) {
            l.add(new ArrayList<>());
            dfs(v, 1, 1, bid++);
        }

        ST st = new ST(rid);
        ST prefixst = new ST(maxd);

        while (M-- > 0) {
            int q = in.nextInt();
            if (q == 0) {
                int v = in.nextInt();
                int x = in.nextInt();
                int d = in.nextInt();

                if (v == 1) {
                    prefixst.add(1, 0, d, x);
                } else if (depth[v] <= d) {
                    // if we extend past root
                    // how much past the root do we extend
                    int over = d - depth[v];
                    prefixst.add(1, 0, over, x);

                    List<Integer> ll = l.get(branchid[v]);
                    if (over < ll.size()) {
                        int first = ll.get(over);
                        st.add(1, range[first][0], range[first][1], x);
                    }

                    // stop when we go past dist
                    if (depth[v]+d < ll.size()) {
                        int stopv = ll.get(depth[v]+d);
                        st.add(1, range[stopv][0], range[stopv][1], -x);
                    }
                } else {
                    List<Integer> ll = l.get(branchid[v]);
                    int startv = ll.get(depth[v]-d-1);
                    st.add(1, range[startv][0], range[startv][1], x);
                    if (depth[v]+d < ll.size()) {
                        int stopv = ll.get(depth[v]+d);
                        st.add(1, range[stopv][0], range[stopv][1], -x);
                    }
                }
            } else {
                int v = in.nextInt();
                long val = st.get(1, range[v][0]);
                long pval = prefixst.get(1, depth[v]);
                out.println(val+pval);
            }
        }

    }

    int rid = 1;
    int[] branchid = new int[100_004];
    int[] depth = new int[100_004];
    int[][] range = new int[100_004][2];
    List<List<Integer>> l = new ArrayList<>();
    int maxd = 0;

    void dfs(int u, int p, int d, int bid) {
        range[u][0] = rid++;
        depth[u] = d;
        branchid[u] = bid;
        maxd = Math.max(maxd, d);
        l.get(bid).add(u);

        for (int v : adj[u]) {
            if (v == p) continue;
            dfs(v, u, d+1, bid);
        }
        range[u][1] = rid++;
    }

    class ST {
        int[] lo;
        int[] hi;
        long[] st;
        ST(int N) {
            lo = new int[4*N];
            hi = new int[4*N];
            st = new long[4*N];
            getBounds(1, 0, N);
        }
        void getBounds(int i, int a, int b) {
            lo[i] = a;
            hi[i] = b;
            if (a == b) return;
            int m = (a+b)>>1;
            getBounds(i<<1, a, m);
            getBounds(i<<1|1, m+1, b);
        }

        void add(int i, int a, int b, int v) {
            if (b < lo[i] || a > hi[i]) return;
            if (a <= lo[i] && hi[i] <= b) {
                st[i] += v;
                return;
            }
            prop(i);
            add(i<<1, a, b, v);
            add(i<<1|1, a, b, v);
        }
        void prop(int i) {
            if (lo[i] == hi[i] || st[i] == 0) return;
            st[i<<1] += st[i];
            st[i<<1|1] += st[i];
            st[i] = 0;
        }

        long get(int i, int a) {
            if (a < lo[i] || a > hi[i]) return 0;
            if (a == lo[i] && a == hi[i]) return st[i];
            prop(i);
            return get(i<<1, a) + get(i<<1|1, a);
        }

    }


    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}
