Hay un árbol (grafo conexo sin ciclos no dirigidos) 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 u v: Imprime el costo del camino de $u$ a $v$.
• 2 u v k: Imprime el $k$-ésimo vértice en el camino de $u$ a $v$. $k$ es menor o igual que el número de vértices en el camino de $u$ a $v$.

Entrada

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

Las siguientes $N-1$ líneas contienen los dos vértices $u$ y $v$ conectados por la arista 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 cada consulta, una por línea.

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

Salida

Imprima los resultados de cada consulta en orden, uno por línea.

Ejemplos

Entrada 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

Salida 1

5
3