Dane jest drzewo składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a wierzchołek $1$ jest korzeniem. Każdy wierzchołek $i$ przechowuje liczbę całkowitą $A[i]$. Początkowo $A[i]$ wynosi $0$.

Należy wykonać następujące zapytania:

• 1 u: Do wszystkich wierzchołków $i$ w poddrzewie o korzeniu w $u$ dodaj $1$ do wartości $A[i]$.
• 2 u v: Do wszystkich wierzchołków $i$ leżących na jedynej najkrótszej ścieżce z $u$ do $v$ dodaj $1$ do wartości $A[i]$. $u$ i $v$ mogą być równe.

Po wykonaniu każdego zapytania wypisz wierzchołek $x$, który minimalizuje wartość $\sum_{y = 1}^{N} A[y] \times dist(x, y)$. $dist(x, y)$ jest równe liczbie krawędzi na ścieżce z $x$ do $y$. Jeśli istnieje wiele możliwych wierzchołków $x$, wypisz ten, który znajduje się najbliżej korzenia (tj. ma najmniejszą odległość od korzenia). Można udowodnić, że taki wierzchołek jest zawsze jednoznacznie określony.

Wejście

Pierwszy wiersz zawiera $N$. ($2 \le N \le 100\,000$)

Kolejne $N-1$ wierszy zawiera krawędzie drzewa. Każdy wiersz zawiera dwie liczby całkowite $u$ i $v$ oddzielone spacją, oznaczające krawędź łączącą wierzchołki $u$ i $v$. ($1 \le u, v \le N, u \neq v$)

Następny wiersz zawiera liczbę zapytań $Q$ do wykonania. ($1 \le Q \le 100\,000$)

Kolejne $Q$ wierszy zawiera zapytania, po jednym w wierszu, w następującym formacie:

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

Wyjście

Dla każdego zapytania, po jego wykonaniu, wypisz w osobnym wierszu wartość, którą należy wypisać. Wyniki należy wypisać w $Q$ wierszach.

Przykład

Wejście

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

Wyjście

2
7
7
1