There is a tree consisting of $N$ vertices. The vertices are numbered from 1 to $N$, and vertex 1 is the root. Each vertex $i$ stores an integer $A[i]$. Initially, $A[i]$ is 0.

The following queries must be processed:

• 1 u: Add 1 to $A[i]$ for all vertices $i$ in the subtree rooted at vertex $u$.
• 2 u v: Add 1 to $A[i]$ for all vertices $i$ on the unique shortest path from vertex $u$ to vertex $v$. $u$ and $v$ may be the same.

After each query, output the vertex $x$ that minimizes $\sum_{y = 1}^{N} A[y] \times dist(x, y)$. $dist(x, y)$ equals the number of edges on the path from $x$ to $y$. If there are multiple such vertices $x$, output the one closest to the root (i.e., with smallest distance from root). It can be proven that such a vertex is always unique.

Input

The first line contains $N$. ($2 \le N \le 100\,000$)

The next $N-1$ lines contain the edges of the tree. Each line consists of two integers $u$ and $v$ separated by a space, meaning there is an edge connecting vertex $u$ and vertex $v$. ($1 \le u, v \le N, u \neq v$)

The next line contains $Q$, the number of queries to be processed. ($1 \le Q \le 100\,000$).

The next $Q$ lines each contain a query, given in one of the following formats:

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

Output

For each query, output the required value in order, one per line, for a total of $Q$ lines.

Examples

Input 1

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

Output 1

2
7
7
1