You are given a tree with n vertices, each initially labeled with the number 0.
You have been given q queries, each in one of the following two forms:
- 1ud : increase the on vertices that adjacent to u by d.
- 2u : find the number on vertex u.
### Input
- The first line contains 2 integers n,q.
- The next n−1 lines, each line contains 2 integers u,v, there is an edge between u and v.
### Output
- Print the answer for each query of type 2.
### Constraints
- 1≤n,q105.
- 1≤u,v≤n.
- 1≤d≤109.
### Example
Input:
32121311123
Output:
1
