有 $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} A_i \times dist(v, i)$。其中 $dist(x, y)$ 表示顶点 $x$ 到顶点 $y$ 路径上的边数。

输入格式

第一行给出 $N$。（$1 \le N \le 200\,000$）

接下来 $N-1$ 行给出树的边。每行有两个空格分隔的数 $u$ 和 $v$，表示连接 $u$ 和 $v$ 的边。（$1 \le u, v \le N$）

接下来一行给出查询个数 $Q$。（$1 \le Q \le 200\,000$）

接下来 $Q$ 行，每行以以下格式之一给出查询：

• 1 u v（$1 \le u, v \le N$）
• 2 u v（$1 \le u, v \le N$）
• 3 v（$1 \le 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