Problem Description

Note: Kitamu is the name of the person who helped create this problem. Also, Kitamu's girlfriend is not Iroha-chan.

Today is summer vacation. Kitamu is out catching bugs with his beloved girlfriend. In fact, catching bugs is a very meaningful joint activity that deepens their love!

Kitamu found an apple tree. This apple tree consists of 1 root, $ N-1 $ leaves or nodes, and $ N-1 $ branches, closely resembling the tree structure in computer science. Hereafter, leaves or nodes, as well as the root, will be referred to as vertices. The root is numbered $ 0 $, and each vertex is numbered $1 \sim N-1$. Initially, Kitamu is at the root.

Since this apple tree produces delicious fruits, sundew bugs come to the vertices. Sundew bugs live in groups and are very intelligent; they disperse and stop at each vertex of a subtree rooted at a certain vertex. For example, when 15 sundew bugs come to a subtree with 3 vertices, they split into 5 bugs each and stop at each vertex. Note that sundew bugs do not come to subtrees where the number of bugs in the group cannot be evenly divided by the number of vertices. Initially, there are 0 sundew bugs at each vertex.

This tree is very tall and unreachable with a bug net, so Kitamu decided to move between vertices to catch sundew bugs. However, it would be a waste of time to constantly go down the tree to check where the bugs are, so he decided to receive $ Q $ instructions from his girlfriend to move between vertices.

The instructions consist of the following two types:

Instruction $ A $ is given in the form:

$ 0 $ $ i $ $ k $

This means that a group of $ k $ sundew bugs has come to the subtree rooted at the $ i $th vertex.

Instruction $ B $ is given in the form:

$ 1 $ $ i $

At this point, Kitamu moves from his current vertex to the $ i $th vertex along the shortest path. During this move, he catches all the sundew bugs at the vertices he passes through, including the starting and ending points, and reports the total number of bugs caught to his girlfriend. Then, Kitamu stays at vertex $ i $ until the next instruction $ B $ is given.

The trial of bug catching that tests their love begins now...

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ C_1 $ $ D_1 $ $ C_2 $ $ D_2 $ $\vdots$ $ C_{N-1} $ $ D_{N-1} $ $ instruction1 $ $ instruction2 $ $\vdots$ $ instructionQ $

Here, integers $ C_i, D_i $ mean that the $ i $th branch of the $ N-1 $ branches connects vertices $ C_i $ and $ D_i $.

Output Format

For each instruction $ B $, report the total number of sundew bugs caught.

Sample Input and Output

Sample Input #1

6 4
0 3
3 1
3 2
4 5
0 5
0 3 9
0 1 2
0 2 5
1 1

Sample Output #1

8

Sample Input #2

9 9
0 5
0 2
0 1
5 8
5 7
5 4
2 3
2 6
0 0 9
0 2 6
0 8 4
1 8
1 1
0 3 8
0 0 144
0 3 32
1 3

Sample Output #2

7
1
110

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 8 \times 10^4$
• $0 \leq C_j, D_j \leq N-1 \ (1 \leq j \leq N-1)$
• The input graph is a tree.
• $0 \leq i \leq N-1$
• $0 \leq k \leq 10^9$
• $ k $ is divisible by the number of vertices in the subtree rooted at vertex $ i $.

Partial Points

• Correctly solving the sample input/output will earn you 1 point.
• Correctly solving all test cases will earn you an additional 1199 points.

Implementation Notes

• This problem is an interactive problem. You must report the number of sundew bugs caught after an instruction $ B $ is given before the next instruction is provided.
• After outputting, you must flush the standard output. Otherwise, there is a possibility of TLE.
• After outputting the answer, the program must terminate immediately. The behavior when not doing so is undefined.
• The behavior when the output answer is wrong is undefined (it may not necessarily be WA).

Explanation

Explanation

Sample Explanation 2

Note that the next instruction will not be given unless you output the answer after an instruction $ B $.

见题面 Input 部分

见题面 Output 部分