Hay un árbol (un grafo conexo sin ciclos) formado por $N$ vértices. Los vértices están numerados del $1$ al $N$, y las aristas están numeradas del $1$ al $N-1$.

Escriba un programa que realice las siguientes dos consultas:

• 1 i c: cambia el costo de la arista $i$ a $c$.
• 2 u v: imprime el costo más grande entre los que existen en el camino simple desde $u$ hasta $v$.

Entrada

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

Las siguientes $N-1$ líneas contienen, para cada arista $i$, los dos vértices $u$ y $v$ que conecta, y su costo $w$.

La siguiente línea contiene el número de consultas $M$ ($1 \le M \le 100{,}000$).

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

El costo de cada arista es siempre un número natural menor o igual a $1{,}000{,}000$.

Salida

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

Ejemplos

Entrada 1

3
1 2 1
2 3 2
3
2 1 2
1 1 3
2 1 2

Salida 1

1
3