$N$ 個の頂点と $M$ 本の辺を持つ、連結な重み付き無向グラフが与えられます。自己ループはなく、任意の頂点対の間には辺が高々 1 本あります。

ある辺を含む最小全域木が少なくとも 1 つ存在する場合、その辺を素晴らしい辺と呼びます。

$Q$ 個のクエリが与えられます。各クエリでは、グラフに新たな辺を 1 本追加した後、新しいグラフの素晴らしい辺の本数を数えてください。一度追加された辺は、グラフにずっと残ります。

連結な重み付き無向グラフの最小全域木とは、すべての頂点を接続し、閉路を持たず、辺の重みの合計が可能な限り小さい、そのグラフの辺の部分集合です。

例えば、次のグラフを考えます。

このグラフには 2 つの最小全域木があり、以下の 2 つの図でその辺を太線で示しています。

グラフには、少なくとも 1 つの最小全域木に現れる素晴らしい辺が 7 本あります：$(2,7)$, $(2,3)$, $(7,1)$, $(7,6)$, $(3,4)$, $(6,5)$, $(4,5)$。

入力

入力の最初の行には、グラフの頂点数と辺数をそれぞれ表す 2 つの整数 $N,M$ ($1\le N,M\le10^5$) が含まれます。

続く $M$ 行のうち $i$ 行目には、3 つの整数 $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$) が 1 つ含まれます。

続く $Q$ 行にはそれぞれ、3 つの整数 $x,y,z$ ($1\le x,y\le N$, $0\le z\le10^9$, $x\ne y$) が含まれ、頂点 $x,y$ を結ぶ重み $z$ の辺を追加するクエリを表します。

初期状態および各クエリの後で、グラフは常に連結で、任意の頂点対は 2 本以上の辺で結ばれていないことが保証されます。

出力

各クエリについて、そのクエリの後のグラフの素晴らしい辺の本数を 1 行に出力してください。

入出力例

入力 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

注記

最初のクエリの後のグラフは次のとおりです。

2 番目のクエリの後のグラフは、問題文のグラフと同じです。