Il y a un arbre (graphe connexe non orienté sans cycle) de $N$ sommets. Les sommets sont numérotés de $1$ à $N$, et les arêtes sont numérotées de $1$ à $N-1$. Initialement, tous les sommets sont blancs.

Écrivez un programme qui effectue les deux types de requêtes suivants :

• 1 i : Change la couleur du sommet $i$ (blanc → noir, noir → blanc).
• 2 : Affiche la distance maximale entre tous les sommets blancs $a$ et $b$. Ici, $a$ et $b$ peuvent être identiques. S'il n'y a aucun sommet blanc, affichez $-1$.

Entrée

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

Les $N-1$ lignes suivantes contiennent, pour chaque arête $i$, les deux sommets $u$ et $v$ qu'elle relie, ainsi que la distance $w$ de l'arête.

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

Les $M$ lignes suivantes décrivent une requête par ligne.

Les distances des arêtes sont toujours des entiers compris entre $-1\,000$ et $1\,000$ inclus.

Sortie

Affichez les résultats de chaque requête de type $2$ dans l'ordre, un par ligne.

Exemples

Entrée 1

3
1 2 1
1 3 1
7
2
1 1
2
1 2
2
1 3
2

Sortie 1

2
2
0
-1