Hay un árbol (grafo conexo sin ciclos) con $N$ vértices. Los vértices están numerados del $1$ al $N$, y las aristas están numeradas del $1$ al $N-1$. Inicialmente, todos los vértices son de color blanco.

Escribe un programa que realice los siguientes dos tipos de consultas:

• 1 i: Cambia el color del vértice $i$ (blanco → negro, negro → blanco).
• 2: Imprime la distancia máxima entre cualquier par de vértices blancos $a$ y $b$ (puede ser el mismo vértice). Si no hay vértices blancos, imprime $-1$.

Entrada

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

Las siguientes $N-1$ líneas contienen los dos vértices $u$ y $v$ conectados por la arista $i$, y la distancia $w$ de la arista.

La siguiente línea contiene $M$ ($1 \le M \le 100{,}000$).

Las siguientes $M$ líneas contienen las consultas, una por línea.

Las distancias de las aristas son siempre enteras mayores o iguales a $-1{,}000$ y menores o iguales a $1{,}000$.

Salida

Para cada consulta de tipo $2$, imprime el resultado en una línea separada, en orden.

Ejemplos

Entrada 1

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

Salida 1

2
2
0
-1