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.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class E {
    static class BIT {
        int[] BIT; // length should be 1+maxVal

        public BIT(int size) {
            BIT = new int[size];
        }

        public int getCumulativeFreq(int idx) {
            int res = 0;
            while (idx > 0) {
                res += BIT[idx];
                idx -= (idx & -idx);
            }
            return res;
        }

        public void update(int idx, int val) {
            while (idx < BIT.length) {
                BIT[idx] += val;
                idx += (idx & -idx);
            }
        }
    }

    static class Node {
        int node;
        int level;

        public Node(int n, int l) {
            node = n;
            level = l;
        }
    }

    static ArrayList<Integer>[] tree;
    static BIT branches;
    static boolean[] vis;
    static int curBITIdx;
    static int[] nodeIndices2;
    static int[] branchEnd;

    public static int dfs(int cur) {
        vis[cur] = true;
        nodeIndices2[cur] = curBITIdx++;
        int end = -1;
        for (Integer ii : tree[cur]) {
            if (!vis[ii]) {
                end = dfs(ii);
            }
        }
        if (end == -1) {
            return branchEnd[cur] = nodeIndices2[cur];
        } else {
            return branchEnd[cur] = end;
        }
    }

    public static void main(String[] args) throws Exception {
        int nodeCnt = nextInt();
        int queryCnt = nextInt();
        tree = new ArrayList[nodeCnt];
        for (int i = 0; i < nodeCnt; i++) {
            tree[i] = new ArrayList<Integer>();
        }
        for (int i = 1; i < nodeCnt; i++) {
            int from = nextInt() - 1;
            int to = nextInt() - 1;
            tree[from].add(to);
            tree[to].add(from);
        }
        BIT levels = new BIT(nodeCnt + 1);
        int[] nodeIndices1 = new int[nodeCnt];
        int[] distanceToRoot = new int[nodeCnt];
        ArrayList<Point> levelRange = new ArrayList<Point>();
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(new Node(0, 0));
        int curLevel = 0;
        int curIdx = 1;
        int curStart = 1;
        vis = new boolean[nodeCnt];
        while (!queue.isEmpty()) {
            Node tmp = queue.removeFirst();
            if (vis[tmp.node])
                continue;
            if (tmp.level > curLevel) {
                levelRange.add(new Point(curStart, curIdx - 1));
                curLevel++;
                curStart = curIdx;
            }
            nodeIndices1[tmp.node] = curIdx++;
            vis[tmp.node] = true;
            distanceToRoot[tmp.node] = tmp.level;
            for (Integer ii : tree[tmp.node]) {
                if (!vis[ii]) {
                    queue.add(new Node(ii, tmp.level + 1));
                }
            }
        }
        levelRange.add(new Point(curStart, curIdx - 1));
        nodeIndices2 = new int[nodeCnt];
        branchEnd = new int[nodeCnt];
        vis = new boolean[nodeCnt];
        branches = new BIT(nodeCnt + 1);
        curBITIdx = 1;
        dfs(0);
        PrintWriter out = new PrintWriter(System.out);
        for (int i = 0; i < queryCnt; i++) {
            int type = nextInt();
            if (type == 0) {
                int node = nextInt() - 1;
                int val = nextInt();
                int dist = nextInt();
                if (dist >= distanceToRoot[node]) {
                    int addTillLvl = Math.min(dist - distanceToRoot[node],
                            levelRange.size() - 1);
                    int st = levelRange.get(0).x;
                    int end = levelRange.get(addTillLvl).y;
                    levels.update(st, val);
                    if (end + 1 < levels.BIT.length)
                        levels.update(end + 1, -val);
//                  System.out.println(st+" "+end+" "+addTillLvl+" "+levelRange.size());
                    st = nodeIndices2[node] - (distanceToRoot[node]-addTillLvl-1);
                    end = Math.min(branchEnd[node], nodeIndices2[node] + dist);
//                  System.out.println(st+" "+end+" "+nodeIndices2[node]+" "+branchEnd[node]);
                    if (st <= end&&node!=0) {
                        branches.update(st, val);
                        if (end + 1 < branches.BIT.length) {
                            branches.update(end + 1, -val);
                        }
                    }

                } else {
                    int st = nodeIndices2[node] - dist;
                    int end = Math.min(branchEnd[node], nodeIndices2[node]
                            + dist);
                    branches.update(st, val);
                    if (end + 1 < branches.BIT.length) {
                        branches.update(end + 1, -val);
                    }
                }
            } else {
                int node = nextInt() - 1;
                out.println(levels.getCumulativeFreq(nodeIndices1[node])
                        + branches.getCumulativeFreq(nodeIndices2[node]));
            }
        }
        out.flush();
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(
            System.in));
    static StringTokenizer tokenizer = new StringTokenizer("");

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

    static double nextDouble() throws Exception {
        return Double.parseDouble(next());
    }

    static String next() throws Exception {
        while (true) {
            if (tokenizer.hasMoreTokens()) {
                return tokenizer.nextToken();
            }
            String s = br.readLine();
            if (s == null) {
                return null;
            }
            tokenizer = new StringTokenizer(s);
        }
    }
}
