E. Little Girl and Problem on Treestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputA 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. InputThe 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.OutputFor each request to print the node value print an integer — the reply to the request.ExamplesInput3 61 21 30 3 1 20 2 3 10 1 5 21 11 21 3Output996Input6 111 22 55 41 61 30 3 1 30 3 4 50 2 1 40 1 5 50 4 6 21 11 21 31 41 51 6Output111711161711
Input3 61 21 30 3 1 20 2 3 10 1 5 21 11 21 3
Output996
['data structures', 'graphs', 'trees', '*2100']