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

Écrivez un programme qui exécute les deux requêtes suivantes :

• 1 i c : changer le coût de l'arête $i$ en $c$.
• 2 u v : afficher le plus grand coût parmi ceux du chemin simple allant de $u$ à $v$.

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 son coût $w$.

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

Les $M$ lignes suivantes contiennent une requête par ligne.

Les coûts des arêtes sont toujours des entiers naturels inférieurs ou égaux à $1\,000\,000$.

Sortie

Pour chaque requête de type $2$, affichez le résultat sur une ligne, dans l'ordre.

Exemples

Entrée 1

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

Sortie 1

1
3