Se da un grafo no dirigido, conectado y ponderado con $N$ vértices y $M$ aristas. El grafo no tiene bucles y entre cualquier par de vértices hay como máximo una arista.

Una arista se llama estupenda si existe al menos un árbol de expansión mínima que la contiene.

Se dan $Q$ consultas. En cada una debes añadir una nueva arista al grafo y después contar el número de aristas estupendas en el nuevo grafo. Ten en cuenta que, una vez añadida, una arista permanece en el grafo para siempre.

Un árbol de expansión mínima de un grafo no dirigido, conectado y ponderado es un subconjunto de sus aristas que conecta todos sus vértices, no contiene ciclos y tiene el menor peso total posible.

Por ejemplo, considera el siguiente grafo:

Tiene 2 árboles de expansión mínima, mostrados en las dos figuras siguientes con sus aristas en negrita:

El grafo tiene 7 aristas estupendas que aparecen en al menos un árbol de expansión mínima: $(2,7)$, $(2,3)$, $(7,1)$, $(7,6)$, $(3,4)$, $(6,5)$ y $(4,5)$.

Entrada

La primera línea de la entrada contiene dos enteros $N,M$ ($1\le N,M\le10^5$), el número de vértices y aristas del grafo, respectivamente.

De las siguientes $M$ líneas, la $i$-ésima contiene tres enteros $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$), que indican que hay una arista de peso $w_i$ entre $u_i,v_i$ en el grafo inicial.

La siguiente línea contiene un entero $Q$ ($1\le Q\le10^5$), el número de consultas.

Cada una de las siguientes $Q$ líneas contiene tres enteros $x,y,z$ ($1\le x,y\le N$, $0\le z\le10^9$, $x\ne y$), que describen una consulta en la que se añade una arista de peso $z$ entre los vértices $x,y$.

Se garantiza que al principio y después de cada consulta el grafo siempre está conectado y ningún par de vértices está conectado por más de una arista.

Salida

Para cada consulta, imprime una línea con el número de aristas estupendas del grafo después de esa consulta.

Ejemplos

Entrada 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

Salida 1

6
7

Nota

Después de la primera consulta, el grafo es el siguiente:

Después de la segunda consulta, el grafo es el mismo que en la descripción del problema.