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<sup class="upper-index">5</sup>) and *q* (1 ≤ *q* ≤ 10<sup class="upper-index">5</sup>) — the number of tree nodes and the number of requests, correspondingly.

Each of the next *n*  -  1 lines contains two integers *u*<sub class="lower-index">*i*</sub> and *v*<sub class="lower-index">*i*</sub> (1 ≤ *u*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub> ≤ *n*, *u*<sub class="lower-index">*i*</sub> ≠ *v*<sub class="lower-index">*i*</sub>), that show that there is an edge between nodes *u*<sub class="lower-index">*i*</sub> and *v*<sub class="lower-index">*i*</sub>. 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<sup class="upper-index">4</sup>, 1 ≤ *d* &lt; *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.
from collections import deque

def update_tree_values(tree, n, v, x, d):
    visited = [False] * (n + 1)
    q = deque([(v, 0)])
    while q:
        curr_node, curr_dist = q.popleft()
        if curr_dist > d:
            break
        visited[curr_node] = True
        tree[curr_node] += x
        for neighbor in graph[curr_node]:
            if not visited[neighbor]:
                q.append((neighbor, curr_dist + 1))

def get_node_value(tree, v):
    return tree[v]

n, q = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

tree = [0] * (n + 1)

for i in range(q):
    query = input().split()
    if query[0] == '0':
        v, x, d = map(int, query[1:])
        update_tree_values(tree, n, v, x, d)
    elif query[0] == '1':
        v = int(query[1])
        print(get_node_value(tree, v))

 	 	 				   	 	   	  	  				