这是一个交互问题。

建议您使用快速的语言来回答这个问题。已经确认可以在C++14 (GCC 5.4.1)中AC。

问题描述

※“きたむー”是帮助出题的人的名字。另外，"きたむー"的女朋友不是"いろはちゃん"。

今天是暑假。"きたむー"和他心爱的女朋友一起来捉虫子。实际上，捉虫子是加深他们之间爱情的非常有意义的合作任务！

"きたむー"发现了一棵苹果树。这棵苹果树有1个根节点、N-1个叶子或者节点和N-1条边，类似于信息科学中的树结构。在这里，叶子或者节点以及根节点被称为顶点。根节点编号为0，每个顶点编号从1到N-1。一开始，"きたむー"在根节点。

从这棵苹果树上可以摘到美味的果实，所以蠢萌虫会飞到各个顶点上。蠢萌虫聪明且生活在群体中，它们会分散停留在以某个顶点为根节点的子树的各个顶点上。例如，当有15只蠢萌虫飞到有3个顶点的子树上时，它们会分成5只一组停留在各个顶点上。注意，蠢萌虫不会飞到顶点数无法整除群体总数的子树中。另外，一开始每个顶点上都没有蠢萌虫。

这棵树非常高大，捉虫网够不到那么高，所以"きたむー"决定在各个顶点之间移动来捉虫子。然而，如果他每次都要下树去确认蠢萌虫的位置，那就太浪费时间了。因此，他决定在女朋友的指示下，移动顶点之间的最短路径来捉虫子。

指示分为以下两种类型：

指示类型 A：

$0$ $i$ $k$

表示第 $i$ 个顶点的子树中飞来了$k$只蠢萌虫。

指示类型 B：

$1$ $i$

此时，"きたむー"将从当前所在的顶点移动到第 $i$ 个顶点，并沿途捕获经过的顶点上的所有蠢萌虫，然后报告给女朋友。然后，他将停留在顶点 $i$，直到下一个指示 B 出现。

为了考察二人之间的爱情，捉虫子的试炼现在开始...

约束条件

• 输入都是整数。
• $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)$
• 输入的图是一棵树。
• $0 \\leq i \\leq N-1$
• $0 \\leq k \\leq 10^{9}$
• $k$ 可以被顶点 $i$ 的子树中的顶点数整除。

部分分

• 通过以下输入输出样例可获得1分。
• 通过所有测试用例可获得额外的1199分。

---

输入

输入从标准输入读取，其格式如下。

$N$ $Q$ $C_1$ $D_1$ $C_2$ $D_2$ $\\vdots$ $C_{N-1}$ $D_{N-1}$ $instruction_1$ $instruction_2$ $\\vdots$ $instruction_Q$

其中，整数 $C_i,\\ D_i$ 表示第 $i$ 条边连接顶点 $C_i$ 和 $D_i$。

输出

每次出现指示 B 时，报告捕获到的蠢萌虫总数。

实现注意事项

• 这是一个交互问题。在给出指示 B 后，直到报告捕获到的蠢萌虫数量，下一条指示才会出现，请注意。
• 输出后，必须刷新标准输出。否则可能会出现 "TLE"。
• 输出答案后，必须立即结束程序。否则行为未定义。
• 输出的答案错误时的行为未定义（不一定是 "WA"）。

---

输入例子 1

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

输出例子 1

8

---

输入例子 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

输出例子 2

7
1
110

请注意，在给出指示 B 后需要输出答案，否则下一条指令将不会出现。

---

解析

解析