Un arbre constitué de $N$ sommets. Les sommets sont numérotés de $0$ à $N-1$. Les arêtes ont des poids entiers non négatifs.

Vous devez effectuer les requêtes suivantes :

• 1 u v w x : Supprimer l'arête reliant $u$ et $v$, et ajouter une arête de poids $x$ reliant $v$ et $w$. Il est garanti que l'arête entre $u$ et $v$ existe. Il est garanti qu'après l'opération, le graphe reste un arbre. ($0 \le x \le 100\,000$)
• 2 k x_1 x_2 ... x_k : Pour les sommets $x_1, x_2, \ldots, x_k$, considérer le chemin simple unique entre $x_i$ et $x_j$ pour tout $1 \le i < j \le k$. Afficher la somme des poids de toutes les arêtes appartenant à l'union de ces chemins. Tous les $x_i$ sont distincts. ($1 \le k \le n$)

Entrée

La première ligne contient la taille de l'arbre $N$. ($2 \le N \le 100\,000$)

Les $N-1$ lignes suivantes contiennent trois entiers $u, v, w$, indiquant qu'il existe une arête de poids $w$ reliant les sommets $u$ et $v$. ($0 \le u, v \le N-1$, $0 \le w \le 100\,000$)

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

Les $Q$ lignes suivantes contiennent les requêtes comme décrites ci-dessus.

La somme des $k$ sur toutes les requêtes de type 2 est comprise entre $1$ et $100\,000$.

Sortie

Afficher les résultats des requêtes de type 2 dans l'ordre, un par ligne.

Exemples

Entrée 1

7
0 1 1
0 2 2
1 3 3
1 4 4
2 5 5
2 6 6
4
1 1 4 5 7
2 3 0 4 6
1 0 2 1 8
2 3 0 4 6

Sortie 1

20
27