A. Queries on the Tree
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a directed tree with N with nodes numbered 1 to N and rooted at node 1. Each node initially contains 0 coins.

You have to handle a total of M operations:

  • 1 L Y : Increase by Y the coins of all nodes which are at a distance L from root.
  • 2 X : Report the sum of coins of all nodes in subtree rooted at node X.
Input

First line contains N and M. Each of the next N - 1 lines contains u and v denoting directed edge from node numbered u to v.

Each of the next M lines contain queries of either Type 1 or 2.

Output

For each query of Type 2, print the required sum.

Constraints

  • 1 ≤ N105
  • 1 ≤ M104
  • 0 ≤ L ≤ Maximum height of tree
  • 0 ≤ Y109
  • 1 ≤ X, u, vN
Examples
Input
5 4
1 2
1 3
3 4
3 5
1 1 2
1 2 3
2 3
2 1
Output
8
10
Note

In first update nodes 2 and 3 are increased by 2 coins each.

In second update nodes 4 and 5 are increased by 3 each.