你有一棵包含 $N$ 个顶点的树。顶点编号为从 $1$ 到 $N$ 的连续整数，第 $i$ 个顶点包含变量 $A_i$。初始时 $A_i = 0$ ($1 \le i \le N$)。

你需要处理 $Q$ 次查询。每次查询属于以下类型之一：

• “1 $u$ $v$”：以顶点 $u$ 为根，考虑顶点 $v$ 的子树，并将该子树中每个顶点 $i$ 的 $A_i$ 增加 $1$。
• “2 $u$ $v$”：对于从 $u$ 到 $v$ 的唯一简单路径上的每个顶点 $i$，将 $A_i$ 增加 $1$。
• “3 $v$”：输出 $\sum_{i=1}^{N} \text{dist}(v, i) \cdot A_i$，其中 $\text{dist}(x, y)$ 表示从顶点 $x$ 到顶点 $y$ 的路径上的边数。

输入格式

第一行包含一个整数 $N$，表示顶点数量 ($1 \le N \le 2 \cdot 10^5$)。

接下来的 $N - 1$ 行包含树的描述。每行包含两个用空格分隔的整数 $u$ 和 $v$，表示存在一条连接 $u$ 和 $v$ 的边 ($1 \le u, v \le N$)。保证给定的图是一棵树。

下一行包含一个整数 $Q$，表示查询数量 ($1 \le Q \le 2 \cdot 10^5$)。

接下来的 $Q$ 行包含查询，每行一个。每个查询以如上所述的格式给出 ($1 \le u, v \le N$)。你可以假设至少存在一个类型为 “3” 的查询。

输出格式

对于每个类型为 “3” 的查询，在单独的一行中输出结果。

样例

样例输入 1

5
4 2
2 5
1 5
1 3
5
2 2 4
3 4
2 1 5
2 5 5
3 2

样例输出 1

1
5