Mamy drzewo (spójny graf nieskierowany bez cykli) złożone z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a krawędzie od $1$ do $N-1$.

Napisz program wykonujący następujące dwa zapytania:

• 1 u v: wypisz koszt ścieżki z $u$ do $v$.
• 2 u v k: wypisz $k$-ty wierzchołek na ścieżce z $u$ do $v$. Liczba $k$ jest nie większa niż liczba wierzchołków na ścieżce z $u$ do $v$.

Wejście

Pierwszy wiersz zawiera $N$ ($2 \le N \le 100{,}000$).

Następne $N-1$ wierszy zawiera po trzy liczby: numery dwóch wierzchołków $u$ i $v$ połączonych $i$-tą krawędzią oraz koszt $w$ tej krawędzi.

Następny wiersz zawiera $M$ ($1 \le M \le 100{,}000$) – liczbę zapytań.

Następne $M$ wierszy zawiera po jednym zapytaniu.

Koszt krawędzi jest zawsze liczbą naturalną nie większą niż $1{,}000{,}000$.

Wyjście

Dla każdego zapytania wypisz wynik w osobnym wierszu, w kolejności występowania.

Przykład

Wejście

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

Wyjście

5
3