$N$ 個の頂点からなる木がある。頂点には 1 から $N$ までの番号が付けられており、頂点 $i$ には整数 $A_i$ が格納されている。初期状態では $A_i = 0$ である。($1 \le i \le N$)

あなたは以下のクエリを合計 $Q$ 回実行しなければならない。

1. 1 u v: 木の根を頂点 $u$ としたとき、頂点 $v$ を根とする部分木のすべての頂点 $i$ の $A_i$ に 1 を加算する。
2. 2 u v: 頂点 $u$ から頂点 $v$ への一意なパス上のすべての頂点 $i$ の $A_i$ に 1 を加算する。
3. 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$ 行に木の辺が与えられる。各行には空白で区切られた 2 つの数 $u$ と $v$ が与えられ、$u$ と $v$ を結ぶ辺があることを意味する。($1 \le u, v \le N$)

次の行にクエリの個数 $Q$ が与えられる。($1 \le Q \le 200{,}000$)

次の $Q$ 行の各行には、以下の形式のいずれかでクエリが 1 つずつ与えられる。

• 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 番目のクエリは 1 回以上与えられる。

出力

各 3 番目のクエリの結果を順に 1 行ずつ出力する。

入出力例

入力 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