Andi 在板上有 $N$ 个齿轮（编号从 $1$ 到 $N$）。每个齿轮上都有一个初始指向正上方的箭头。某些齿轮对可能相互接触。如果我们构建一个图，其中每个齿轮是一个节点，并将每对接触的齿轮用边连接起来，那么这个图的结构是一棵树。例如，下图是一个 $N=4$ 的齿轮配置示例，其中齿轮 $2$ 与所有其他齿轮接触。

标准齿轮旋转规则适用：假设齿轮 $u$ 与另一个齿轮 $v$ 接触，如果齿轮 $u$ 顺时针旋转 $\alpha$ 度，则齿轮 $v$ 将逆时针旋转 $\alpha$ 度，反之亦然。

Andi 想要执行三种操作：

1. 从板上取下一个齿轮。
2. 将一个齿轮放回板上的原始位置。执行此操作时，Andi 将齿轮放回，使其箭头指向与移除时相同的角度。假设这总是可以做到的，即你不需要考虑齿轮的机械结构。
3. 将一个齿轮顺时针旋转 $\alpha$ 度。

令 $\delta_u$ 为 $Q$ 次操作完成后齿轮 $u$ 的箭头角度（顺时针，模 $360$）。Andi 想知道所有 $u$ 的 $\delta_u$ 之和。此外，由于旋转齿轮需要大量工作，Andi 还想知道他每次执行第 $3$ 类操作（旋转齿轮）所需的能量。Andi 执行第 $3$ 类操作所需的能量定义为：旋转的齿轮数量 $\times$ 旋转的角度。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 100000$)，表示齿轮的数量。接下来的 $N-1$ 行，每行包含两个整数：$u, v$ ($1 \le u, v \le N; u \neq v$)，表示齿轮 $u$ 和齿轮 $v$ 相互接触。保证连接的齿轮结构形成一棵树。下一行包含一个整数 $Q$ ($1 \le Q \le 100000$)，表示操作的数量。接下来的 $Q$ 行，每行表示一个按顺序执行的操作。每个操作以以下格式之一给出：

• 两个整数：$1 \ x$ ($1 \le x \le N$)。这意味着此操作将齿轮 $x$ 从板上的位置取下。保证齿轮 $x$ 当前在板上。
• 两个整数：$2 \ x$ ($1 \le x \le N$)。这意味着此操作将齿轮 $x$ 放回板上的原始位置。保证齿轮 $x$ 当前不在板上。
• 三个整数：$3 \ x \ \alpha$ ($1 \le x \le N; 0 \le \alpha \le 359$)。这意味着此操作将齿轮 $x$ 顺时针旋转 $\alpha$ 度。保证齿轮 $x$ 当前在板上。

输出格式

对于每个第 $3$ 类操作，按输入顺序，在一行中输出旋转齿轮所需的能量。最后，在一行中输出所有 $u$ 的 $\delta_u$ 之和。

样例

样例输入 1

4
1 2
2 3
2 4
8
3 2 160
1 2
3 1 10
3 3 10
3 4 10
2 2
1 1
3 3 15

样例输出 1

640
10
10
10
45
805

说明

样例的齿轮结构如图所示。下表说明了每次操作后每个齿轮的状态。

因此，所有 $u$ 的 $\delta_u$ 之和为 $210 + 145 + 225 + 225 = 805$。