$N$개의 정점과 $M$개의 간선을 가진 연결된 가중 무방향 그래프가 주어진다. 그래프에는 자기 루프가 없으며, 임의의 정점 쌍 사이에는 간선이 최대 하나 있다.

어떤 간선을 포함하는 최소 신장 트리가 적어도 하나 있다면, 그 간선을 멋진 간선이라고 한다.

$Q$개의 질의가 주어진다. 각 질의에서는 주어진 그래프에 새 간선을 하나 추가한 다음 새 그래프의 멋진 간선 수를 세어야 한다. 한 번 추가한 간선은 그래프에 영원히 남는다.

연결된 가중 무방향 그래프의 최소 신장 트리는 모든 정점을 연결하고 사이클이 없으며 총 간선 가중치가 가능한 한 최소인 간선 부분집합이다.

예를 들어 다음 그래프를 생각해 보자:

이 그래프에는 최소 신장 트리가 2개 있으며, 아래 두 그림에서 그 간선을 굵게 표시했다:

그래프에는 적어도 하나의 최소 신장 트리에 나타나는 멋진 간선이 7개 있다: $(2,7)$, $(2,3)$, $(7,1)$, $(7,6)$, $(3,4)$, $(6,5)$, $(4,5)$.

입력

입력의 첫째 줄에는 그래프의 정점 수와 간선 수를 각각 나타내는 두 정수 $N,M$ ($1\le N,M\le10^5$)이 주어진다.

다음 $M$개의 줄 중 $i$번째 줄에는 세 정수 $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$)가 주어진다. 이는 초기 그래프에 정점 $u_i,v_i$를 연결하는 가중치 $w_i$의 간선이 있음을 뜻한다.

다음 줄에는 질의 수를 나타내는 정수 $Q$ ($1\le Q\le10^5$)가 주어진다.

다음 $Q$개의 줄에는 각각 세 정수 $x,y,z$ ($1\le x,y\le N$, $0\le z\le10^9$, $x\ne y$)가 주어지며, 정점 $x,y$를 연결하는 가중치 $z$의 간선을 추가하는 질의를 나타낸다.

처음과 각 질의 이후에 그래프는 항상 연결되어 있고, 어떤 정점 쌍도 두 개 이상의 간선으로 연결되지 않음이 보장된다.

출력

각 질의에 대해 그 질의 이후 그래프의 멋진 간선 수를 한 줄에 출력하라.

예제

입력 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

출력 1

6
7

참고

첫 번째 질의 이후의 그래프는 다음과 같다:

두 번째 질의 이후의 그래프는 문제 설명의 그래프와 같다.