有一棵由 $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$ 行描述树的边。每行包含两个空格分隔的整数 $u$ 和 $v$，表示连接顶点 $u$ 和顶点 $v$ 的一条边（$1 \le u, v \le N$，$u \neq v$）。

接下来一行包含一个整数 $Q$，表示需要执行的查询数量（$1 \le Q \le 100\,000$）。

接下来 $Q$ 行，每行描述一个查询，格式如下：

• 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