Hay un árbol formado por $N$ vértices. Los vértices están numerados del $0$ al $N-1$. Las aristas tienen pesos enteros no negativos.

Se deben realizar las siguientes consultas:

• 1 u v w x: Elimina la arista que conecta $u$ y $v$, y agrega una arista de peso $x$ que conecta $v$ y $w$. Se garantiza que la arista entre $u$ y $v$ existe. Se garantiza que después de la operación el grafo sigue siendo un árbol. ($0 \le x \le 100\,000$)
• 2 k x_1 x_2 ... x_k: Dados los vértices $x_1, x_2, \ldots, x_k$, considera el único camino simple que conecta $x_i$ y $x_j$ para todos los pares $1 \le i < j \le k$. Imprime la suma de los pesos de todas las aristas que pertenecen a la unión de estos caminos simples. Todos los $x_i$ son distintos. ($1 \le k \le n$)

Entrada

La primera línea contiene el tamaño del árbol $N$. ($2 \le N \le 100{,}000$)

Las siguientes $N-1$ líneas contienen tres enteros $u, v, w$, que indican que existe una arista de peso $w$ que conecta los vértices $u$ y $v$. ($0 \le u, v \le N - 1$, $0 \le w \le 100{,}000$)

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

Las siguientes $Q$ líneas contienen consultas como las descritas anteriormente.

La suma de los valores de $k$ de las consultas de tipo $2$ es al menos $1$ y como máximo $100{,}000$.

Salida

Imprime los resultados de las consultas de tipo $2$ en orden, cada uno en una línea separada.

Ejemplos

Entrada 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

Salida 1

20
27