Dane jest drzewo (spójny graf nieskierowany bez cykli) składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a krawędzie od $1$ do $N-1$. Początkowo wszystkie wierzchołki są białe.

Napisz program wykonujący następujące dwa rodzaje zapytań:

• 1 i: Zmień kolor wierzchołka $i$ (biały → czarny, czarny → biały).
• 2: Wypisz największą odległość pomiędzy dowolnymi dwoma białymi wierzchołkami $a$ i $b$ (dopuszczalne jest $a = b$). Jeśli nie ma żadnego białego wierzchołka, wypisz $-1$.

Wejście

W pierwszym wierszu podana jest liczba $N$ ($2 \le N \le 100{,}000$).

W kolejnych $N-1$ wierszach podane są liczby $u$ i $v$ – numery wierzchołków połączonych przez $i$-tą krawędź, oraz $w$ – odległość na tej krawędzi.

W następnym wierszu podana jest liczba $M$ ($1 \le M \le 100{,}000$) – liczba zapytań.

W kolejnych $M$ wierszach podane są zapytania, po jednym w wierszu.

Odległości na krawędziach są zawsze liczbami całkowitymi z przedziału $[-1{,}000, 1{,}000]$.

Wyjście

Dla każdego zapytania typu $2$ wypisz wynik w osobnym wierszu, w kolejności występowania.

Przykład

Wejście 1

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

Wyjście 1

2
2
0
-1