Little Girl and Problem on Trees

Description:

Input:

The first line contains integers n (2 ≤ n ≤ 10⁵) and q (1 ≤ q ≤ 10⁵) — the number of tree nodes and the number of requests, correspondingly.

Each of the next n  -  1 lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i), that show that there is an edge between nodes u_i and v_i. 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⁴, 1 ≤ d < 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.

Output:

For each request to print the node value print an integer — the reply to the request.

Sample Input:

3 6
1 2
1 3
0 3 1 2
0 2 3 1
0 1 5 2
1 1
1 2
1 3

Sample Output:

9
9
6

Sample Input:

6 11
1 2
2 5
5 4
1 6
1 3
0 3 1 3
0 3 4 5
0 2 1 4
0 1 5 5
0 4 6 2
1 1
1 2
1 3
1 4
1 5
1 6

Sample Output:

11
17
11
16
17
11