CF276E.Little Girl and Problem on Trees

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$ .

The first line contains integers $n$ ( $2<=n<=10^{5}$ ) and $q$ ( $1<=q<=10^{5}$ ) — the number of tree nodes and the number of requests, correspondingly.

Each of the next $n-1$ lines contains two integers $u_{i}$ and $v_{i}$ ( $1<=u_{i},v_{i}<=n$ , $u_{i}≠v_{i}$ ), that show that there is an edge between nodes $u_{i}$ and $v_{i}$ . 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<=10^{4}$ , 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.

For each request to print the node value print an integer — the reply to the request.