在 Baekjoon Online Judge 上，有一系列关于处理树上查询的问题。我们 KAISTians 很荣幸能提供该系列的第十七个版本。

给定一棵有 $N$ 个顶点的树。每个顶点的编号从 $1$ 到 $N$。树的根节点为 $1$。

每个顶点都可以住人。设 $A[i]$ 为住在顶点 $i$ 的人数。初始时，对于所有 $1 \le i \le N$，都有 $A[i] = 0$。

编写一个程序来处理以下 $Q$ 个查询：

• $1\ u$：对于以 $u$ 为根的子树中的所有顶点 $i$，将 $A[i]$ 加 $1$。
• $2\ u\ v$：对于连接顶点 $u$ 和 $v$ 的唯一最短路径上的所有顶点 $i$，将 $A[i]$ 加 $1$。注意 $u$ 和 $v$ 可能相等。

每次查询后，输出一个顶点 $x$，使得 $\sum_{y=1}^{N} A[y] \times dist(x, y)$ 的值最小，其中 $dist(x, y)$ 是 $x$ 和 $y$ 之间路径上的边数。如果存在多个这样的顶点，则输出距离根节点（顶点 $1$）最近的那个顶点。可以证明这样的顶点是唯一的。换句话说，我们需要找到一个使所有人聚集所需的总距离最小的顶点。

输入格式

第一行包含一个整数 $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