Il y a un arbre composé de $N$ sommets. Les sommets sont numérotés de $1$ à $N$, et le sommet $1$ est la racine. Chaque sommet $i$ contient un entier $A[i]$. Initialement, $A[i] = 0$.

Les requêtes suivantes doivent être effectuées :

• 1 u : ajoute 1 à $A[i]$ pour tous les sommets $i$ du sous-arbre enraciné au sommet $u$.
• 2 u v : ajoute 1 à $A[i]$ pour tous les sommets $i$ se trouvant sur l'unique plus court chemin entre le sommet $u$ et le sommet $v$. Il est possible que $u$ et $v$ soient identiques.

Après chaque requête, affichez le sommet $x$ qui minimise la valeur de $\sum_{y = 1}^{N} A[y] \times dist(x, y)$. $dist(x, y)$ est égal au nombre d'arêtes sur le chemin de $x$ à $y$. S'il y a plusieurs sommets $x$ possibles, affichez celui dont la distance à la racine est la plus petite. On peut montrer qu'un tel sommet est toujours unique.

Entrée

La première ligne contient $N$. ($2 \le N \le 100\,000$)

Les $N-1$ lignes suivantes contiennent les arêtes de l'arbre. Chaque ligne contient deux entiers $u$ et $v$ séparés par une espace, représentant une arête reliant le sommet $u$ et le sommet $v$. ($1 \le u, v \le N, u \neq v$)

La ligne suivante contient $Q$, le nombre de requêtes à effectuer. ($1 \le Q \le 100\,000$).

Les $Q$ lignes suivantes contiennent les requêtes, une par ligne, sous l'un des formats suivants :

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

Sortie

Affichez sur $Q$ lignes, dans l'ordre, la valeur à sortir après chaque requête.

Exemples

Entrée 1

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

Sortie 1

2
7
7
1