Dane jest drzewo o $N$ wierzchołkach. Wierzchołki są ponumerowane od $0$ do $N-1$. Krawędzie mają nieujemne wagi całkowite.

Należy wykonać następujące zapytania:

• 1 u v w x: usuń krawędź łączącą $u$ i $v$, a następnie dodaj krawędź o wadze $x$ łączącą $v$ i $w$. Gwarantowane, że krawędź między $u$ i $v$ istnieje. Po operacji graf nadal jest drzewem. ($0 \le x \le 100\,000$)
• 2 k x_1 x_2 ... x_k: dla wierzchołków $x_1, x_2, \ldots, x_k$ rozważmy wszystkie unikalne ścieżki proste łączące $x_i$ i $x_j$ dla $1 \le i < j \le k$. Należy wypisać sumę wag wszystkich krawędzi należących do sumy mnogościowej tych ścieżek. Wszystkie $x_i$ są różne. ($1 \le k \le n$)

Wejście

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

Kolejne $N-1$ wierszy zawiera trzy liczby całkowite $u, v, w$, oznaczające istnienie krawędzi o wadze $w$ łączącej wierzchołki $u$ i $v$. ($0 \le u, v \le N - 1$, $0 \le w \le 100{,}000$)

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

Kolejne $Q$ wierszy zawiera zapytania opisane powyżej.

Suma wartości $k$ ze wszystkich zapytań typu $2$ wynosi co najmniej $1$ i co najwyżej $100{,}000$.

Wyjście

Wypisz wyniki zapytań typu $2$ w kolejności ich wystąpienia, każdy w osobnym wierszu.

Przykład

Wejście 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

Wyjście 1

20
27