Hay un árbol con $N$ vértices. Los vértices están numerados del $1$ al $N$, y el vértice $1$ es la raíz. Cada vértice $i$ tiene almacenado un entero $A[i]$. Inicialmente, $A[i]$ es $0$.

Se deben realizar las siguientes consultas:

• 1 u: Suma $1$ a $A[i]$ de todos los vértices $i$ del subárbol con raíz en el vértice $u$.
• 2 u v: Suma $1$ a $A[i]$ de todos los vértices $i$ en el único camino más corto desde el vértice $u$ hasta el vértice $v$. $u$ y $v$ pueden ser iguales.

Después de realizar cada consulta, imprime el vértice $x$ que minimiza el valor de $\sum_{y = 1}^{N} A[y] \times dist(x, y)$, donde $dist(x, y)$ es igual al número de aristas en el camino desde $x$ hasta $y$. Si hay varios vértices $x$ posibles, imprime el vértice cuya distancia desde la raíz sea la más cercana. Se puede demostrar que dicho vértice siempre es único.

Entrada

La primera línea contiene $N$. ($2 \le N \le 100\,000$)

Las siguientes $N-1$ líneas contienen las aristas del árbol. Cada línea contiene dos enteros $u$ y $v$ separados por un espacio, que representan una arista que conecta los vértices $u$ y $v$. ($1 \le u, v \le N, u \neq v$)

La siguiente línea contiene la cantidad de consultas a realizar $Q$. ($1 \le Q \le 100\,000$)

Las siguientes $Q$ líneas contienen las consultas, una por línea, con el siguiente formato:

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

Salida

Imprime $Q$ líneas, en orden, con el valor que se debe imprimir después de realizar cada consulta.

Ejemplos

Entrada

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

Salida

2
7
7
1