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.
n, q = input().split()
n = int(n)
q = int(q)
arestas = {}
soma = {}
visitados = {}
n -= 1
def somatorio(v, x, d):
    global arestas, soma, visitados
    if(v not in visitados):
        soma[v] += x
        visitados[v] = True
    if(d == 1):
        for i in arestas[v]:
            if(i not in visitados):
                soma[i] += x
                visitados[i] = True
    elif(d > 0):
        for i in arestas[v]:
            if(i not in visitados):
                soma[i] += x
                visitados[i] = True
                somatorio(i, x, d-1)
                
        
    
while(n > 0):
    u, v = input().split()
    if(u in arestas):
        arestas[u][v] = v
    else:
        soma[u] = 0
        arestas[u] = {}
        arestas[u][v] = v
    if(v in arestas):
        arestas[v][u] = u
    else:
        soma[v] = 0
        arestas[v] = {}
        arestas[v][u] = v
    n -= 1
while(q > 0):
    req = input().split()
    if(req[0] == "1"):
        print(soma[req[1]])
    else:
        visitados = {}
        somatorio(req[1], int(req[2]), int(req[3]))        
    q -= 1
  			  	  	   	 	 	 		 	   				