$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$ 行には、木の構造が与えられる。各行には空白区切りで2つの整数 $u, v$ が含まれ、これは $u$ と $v$ を結ぶ辺が存在することを意味する ($1 \le u, v \le N$)。与えられるグラフは木であることが保証されている。

次の行には、クエリ数 $Q$ ($1 \le Q \le 2 \cdot 10^5$) が与えられる。

続く $Q$ 行にはクエリが1行ずつ与えられる。各クエリは上記で説明した形式のいずれかである ($1 \le u, 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