$N$ 個の頂点からなる木がある。頂点には 1 から $N$ までの番号が付けられており、頂点 1 は根である。各頂点 $i$ には整数 $A[i]$ が格納されている。最初に $A[i]$ は 0 である。

次のようなクエリを実行する必要がある。

• 1 u: 頂点 $u$ を根とする部分木のすべての頂点 $i$ の $A[i]$ に 1 を加える。
• 2 u v: 頂点 $u$ から頂点 $v$ への唯一の最短経路上にあるすべての頂点 $i$ の $A[i]$ に 1 を加える。$u$ と $v$ は同じでもよい。

各クエリを実行した後、$\sum_{y = 1}^{N} A[y] \times dist(x, y)$ の値を最小にする頂点 $x$ を出力する。$dist(x, y)$ は $x$ から $y$ への経路に存在する辺の数に等しい。可能な頂点 $x$ が複数ある場合は、根からの距離が最も近い頂点を出力する。そのような頂点は常に一意であることが証明できる。

入力

最初の行に $N$ が与えられる。($2 \le N \le 100\,000$)

次の $N-1$ 行には木の辺が与えられる。各行は空白で区切られた2つの整数 $u$ と $v$ からなり、頂点 $u$ と頂点 $v$ を結ぶ辺を表す。($1 \le u, v \le N, u \neq v$)

次の行には、実行する必要のあるクエリの個数 $Q$ が与えられる。($1 \le Q \le 100\,000$)

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

• 1 u ($1 \le u \le N$)
• 2 u v ($1 \le u, v \le N$)

出力

クエリを実行した後に出力すべき値を $Q$ 行に順に出力する。

入出力例

入力 1

7
1 6
1 7
7 3
3 2
7 5
5 4
4
1 2
1 4
1 6
2 6 7

出力 1

2
7
7
1