Dany jest spójny, ważony graf nieskierowany o $N$ wierzchołkach i $M$ krawędziach. Graf nie ma pętli, a między każdą parą wierzchołków jest najwyżej jedna krawędź.

Krawędź nazywamy świetną, jeśli istnieje co najmniej jedno minimalne drzewo rozpinające zawierające tę krawędź.

Danych jest $Q$ zapytań. W każdym zapytaniu należy dodać jedną nową krawędź do grafu, a następnie policzyć świetne krawędzie w nowym grafie. Zauważ, że dodana krawędź pozostaje w grafie na zawsze.

Minimalne drzewo rozpinające spójnego, ważonego grafu nieskierowanego jest podzbiorem jego krawędzi, który łączy wszystkie wierzchołki, nie zawiera cykli i ma najmniejszą możliwą sumę wag krawędzi.

Na przykład rozważmy następujący graf:

Ma on 2 minimalne drzewa rozpinające, pokazane na dwóch poniższych rysunkach, których krawędzie są pogrubione:

Graf ma 7 świetnych krawędzi, występujących w co najmniej jednym minimalnym drzewie rozpinającym: $(2,7)$, $(2,3)$, $(7,1)$, $(7,6)$, $(3,4)$, $(6,5)$ i $(4,5)$.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $N,M$ ($1\le N,M\le10^5$), oznaczające odpowiednio liczbę wierzchołków i krawędzi grafu.

W kolejnych $M$ wierszach $i$-ty zawiera trzy liczby całkowite $u_i,v_i,w_i$ ($1\le u_i,v_i\le N$; $0\le w_i\le10^9$; $u_i\ne v_i$), wskazujące, że w początkowym grafie jest krawędź między $u_i,v_i$ o wadze $w_i$.

Następny wiersz zawiera jedną liczbę całkowitą $Q$ ($1\le Q\le10^5$), oznaczającą liczbę zapytań.

Każdy z kolejnych $Q$ wierszy zawiera trzy liczby całkowite $x,y,z$ ($1\le x,y\le N$, $0\le z\le10^9$, $x\ne y$), opisujące zapytanie dodające krawędź o wadze $z$ między wierzchołkami $x,y$.

Gwarantuje się, że na początku i po każdym zapytaniu graf jest spójny i żadna para wierzchołków nie jest połączona więcej niż jedną krawędzią.

Wyjście

Dla każdego zapytania wypisz jeden wiersz zawierający liczbę świetnych krawędzi w grafie po tym zapytaniu.

Przykład

Wejście 1

7 10
2 7 1
5 6 3
4 5 4
6 7 5
3 4 5
1 7 6
1 2 9
1 3 9
1 4 9
1 5 9
2
1 6 9
2 3 2

Wyjście 1

6
7

Uwagi

Po pierwszym zapytaniu graf wygląda następująco:

Po drugim zapytaniu graf jest taki sam jak graf w treści zadania.