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

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

• 1 u v : Affiche le coût du chemin de $u$ à $v$.
• 2 u v k : Affiche le $k$-ième sommet sur le chemin de $u$ à $v$. $k$ est inférieur ou égal au nombre de sommets sur le chemin 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 de requêtes $M$ ($1 \le M \le 100\,000$).

Les $M$ lignes suivantes décrivent les requêtes, une par ligne.

Le coût d'une arête est toujours un entier naturel inférieur ou égal à $1\,000\,000$.

Sortie

Afficher les résultats de chaque requête dans l'ordre, un par ligne.

Exemples

Entrée 1

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
2
1 4 6
2 4 6 4

Sortie 1

5
3