In a gamified data-structures lab at UMT University, students model the campus network as a rooted tree. Every node initially holds 0 coins. During the experiment they must process ~M~ operations of two types:

• Type 1 - mass deposit 1 L Y: add ~Y~ coins to every node whose distance from the root is exactly ~L~.

• Type 2 - query subtree 2 X: output the total number of coins currently stored in the subtree rooted at node ~X~.

Your task is to efficiently support these operations and output the result for each Type 2 query.

Input

Input The first line contains two integers ~N~ and ~M~ ~(1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^4)~ - the number of nodes and the number of operations.

The next ~N~ - 1 lines contain each two integers u, v that denote an edge between the nodes ~u~ and ~v~.

The next ~M~ lines each describe a query:

• Type 1: ~1~ ~L~ ~Y~ - add ~Y~ coins to all nodes at depth ~L~ from the root.

• Type 2: ~2~ ~X~ - output the total coins in the subtree of node ~X~.

The tree is undirected but rooted at node 1. The input guarantees a valid tree.

Output

For each query of Type 2, output the corresponding sum on a separate line.

Constraints

• 0 ≤ ~L~ ≤ maximum height of the tree

• 0 ≤ ~Y~ ≤ ~10^9~

• 1 ≤ ~X~, ~u~, ~v~ ≤ ~N~

Sample Input 1

5 4
1 2
1 3
3 4
3 5
1 1 2
1 2 3
2 3
2 1

Sample Ouput 1

8
10