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.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    private static void debug(Object... args) {
        //System.out.println(Arrays.deepToString(args));
    }
    private static final int MAX = 100001;
    private static BIT cbit;
    private static final Map<Integer, BIT> bits = new HashMap<Integer, BIT>();
    private static final int[]dg=new int[MAX];
    private static final int[]brch=new int[MAX];
    private static final int[]dist=new int[MAX];
    private static final List<Integer>[]adj = new ArrayList[MAX];
    public static void main(String[] rags) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        for(int i=0;i<n;i++) adj[i]=new ArrayList<Integer>();
        for(int i=0;i<n-1;i++) {
            st = new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken())-1;
            int b=Integer.parseInt(st.nextToken())-1;
            dg[a]--;
            dg[b]--;
            adj[a].add(b);
            adj[b].add(a);
        }
        Arrays.sort(dg,0,n);
        int rt = 0;
        int mdg = -1;
        for(int i=1;i<n;i++) {
            if(mdg < dg[i]) {
                mdg = dg[i];
                rt = i;
            }
        }
        build(rt);
        debug(rt);
        debug(brch);
        debug(dist);
        debug(bits);
        debug(cbit);
        for(int i=0;i<m;i++) {
            st = new StringTokenizer(br.readLine());
            int tp = Integer.parseInt(st.nextToken());
            switch (tp) {
            case 0: 
                debug("case update");
                int v = Integer.parseInt(st.nextToken())-1;
                int x = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());
                
                debug(brch[v]);
                debug(dist[v]);
                debug(bits.get(brch[v]));
                debug(cbit);
                
                if(d-dist[v] >= 0 && v!=rt) {
                    cbit.update(d-dist[v]+1,x);
                    bits.get(brch[v]).update(d-dist[v],-x);
                }
                int frm = Math.max(1, dist[v]-d);
                int to = Math.min(bits.get(brch[v]).N, dist[v]+d);
                bits.get(brch[v]).update(to,x);
                bits.get(brch[v]).update(frm-1,-x);
                debug("after");
                debug(bits.get(brch[v]));
                debug(cbit);
                
                break;
            case 1:
                debug("case read");
                int v1 = Integer.parseInt(st.nextToken())-1;
                int p2 = 0;
                if(v1!=rt) {
                    p2 = cbit.read(dist[v1]+1);
                }
                int p1 = bits.get(brch[v1]).read(dist[v1]);
                debug(brch[v1]);
                debug(bits.get(brch[v1]));
                debug(cbit);
                pw.println(p1 + p2);
            }
        }
        pw.flush();
    }
    private static void build(int rt) {
        int bid = 1;
        brch[rt]=bid;
        dist[rt]=1;
        int maxdist = -1;
        for(int nd : adj[rt]) {
            int bsz = buildBranch(nd,1,bid+1);
            bits.put(bid+1,new BIT(bsz));
            bid++;
            maxdist = Math.max(maxdist, bsz);
        }
        cbit = new BIT(maxdist+1);
        bits.put(1, cbit);
    }
    private static int buildBranch(int nd, int i,int bid) {
        brch[nd]=bid;
        dist[nd]=i;
        for(int c : adj[nd]) {
            if(brch[c]!=0) continue;
            return buildBranch(c, i+1, bid);
        }
        return i;
    }
    private static final class BIT {
        int[]v;
        int N;
        public BIT(int n) {
            v = new int[n+1];
            N=n;
        }
        public void update(int n, int x) {
            update1(1,x);
            update1(n+1,-x);
        }
        public void update1(int n, int x) {
            if(n<=0) return;
            while(n <= N) {
                v[n]+=x;
                n += (n & -n);
            }
        }
        public int read(int n) {
            int sum = 0;
            while(n > 0) {
                sum += v[n];
                n -= (n & -n);
            }
            return sum;
        }
        @Override
        public String toString() {
            return Arrays.toString(v);
        }
    }
}
