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 LittleGirlProblemOnTrees {
    static ArrayList<Integer>[] graph;
    static int[] order, depth;
    static int[] depthSize;
    static int[] in, sz;
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out, false);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        graph = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for(int i = 1; i < n; i++) {
            int u = scanner.nextInt()-1;
            int v = scanner.nextInt()-1;
            graph[u].add(v); graph[v].add(u);
        }
        getBFSOrder(n);
        sz = new int[n];
        in = new int[n];
        getDFSOrder(0, 0);
        SegTree bfs = new SegTree(n, 0, n-1);
        SegTree dfs = new SegTree(n, 0, n-1);
        for(int i = 0; i < q; i++) {
            int type = scanner.nextInt();
            int v = scanner.nextInt()-1;
            if (type == 0) {
                int x = scanner.nextInt();
                int d = scanner.nextInt();
                int diff = d - depth[v];
                if (diff >= 0) {
                    //bfs update
                    bfs.update(1, 0, depthSize[diff]-1, x);
                }
                int upper = Math.max(d-depth[v]+1,depth[v]-d);
                int du = depth[v] - upper;
                int lower = Math.min(sz[v],d);
                if (diff < lower + depth[v]) {
                    dfs.update(1, in[v] - du, in[v] + lower, x);
                }
            } else {
                out.println((dfs.query(1, in[v]) + bfs.query(1, order[v])));
            }
        }
        out.flush();
    }
    static int cnt = 0;
    static void getDFSOrder(int cur, int p) {
        sz[cur]= 0;
        in[cur] = cnt++;
        for(int edge: graph[cur]) {
            if (edge==p) continue;
            getDFSOrder(edge, cur);
            sz[cur] += sz[edge]+1;
        }
    }
    static void getBFSOrder(int n) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        order = new int[n];
        depthSize = new int[n + 1];
        int p = 0;
        depthSize[0] = 1;
        queue.offer(0);
        depth = new int[n];
        Arrays.fill(depth, -1);
        depth[0] = 0;
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            order[cur] = p++;
            for(int edge: graph[cur]) {
                if (depth[edge] != -1) continue;
                depth[edge] = depth[cur]+1;
                depthSize[depth[edge]]++;
                queue.offer(edge);
            }
        }
        for(int i = 1; i <= n; i++) {
            depthSize[i] = depthSize[i-1] + depthSize[i];
        }
    }
    static class SegTree {
        int[] hi, lo, delta;
        public SegTree(int ss, int l, int r) {
            hi = new int[4 * ss+1];
            lo = new int[4 * ss+1];
            delta = new int[4 * ss+1];
            init(1, l, r);
        }
        public void init(int cur, int l, int r) {
            hi[cur] = r;
            lo[cur] = l;
            if (l == r) return;
            int mid = (l + r)/2;
            init(cur*2, l, mid);
            init(cur*2+1, mid + 1, r);
        }
        public void prop(int cur) {
            delta[cur*2] += delta[cur];
            delta[cur*2+1] += delta[cur];
            delta[cur] = 0;
        }
        public void update(int cur, int l, int r, int amt) {
            if (l > hi[cur] || r < lo[cur]) return;
            if (r >= hi[cur] && l <= lo[cur]) {
                delta[cur] +=  amt;
                return;
            }
            prop(cur);
            update(cur*2,l,r,amt);
            update(cur*2+1, l, r, amt);
        }
        public int query(int cur, int t) {
            if (hi[cur] == t && lo[cur] == t) return delta[cur];
            int mid = (hi[cur] + lo[cur])/2;
            prop(cur);
            if (t <= mid) return query(cur*2, t);
            else return query(cur*2+1, t);
        }
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        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());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
