给定一个有 $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

说明

第一次询问后，图如下所示：

第二次询问后，图与题目描述中的图相同。