問題文

入力の最初に正整数 $N$ と非負整数 $M$ と、（自己ループや多重辺を持たない）$N$ 頂点 $M$ 辺の重み付き無向グラフ $G$ が与えられます。

以下のような問題を考えます。

入力に非負整数 $R$ が与えられます。

$G$ から重みが $R$ より大きい辺を削除して得られる重み付き無向グラフの連結成分の個数を求めてください。（以下、この値をこの問題に対する答えと呼ぶ）

入力に正整数 $T$ が与えられます。$T$ 個の問題に答えてください。

背景

位相的データ解析（Topological Data Analysis）という分野では重み付き無向グラフにパーシステントホモロジーという次数付きの不変量が定義され広く応用されています。次数を１つ固定するごとにパーシステントホモロジーは非負実数で添字付けられた単体的ホモロジーと呼ばれる幾何学的不変量の系列データを与え、それ自身やその双対的な不変量のなす系列データはその他の幾何学的不変量をある意味で近似する^{[1] Theorem 3.5, Theorem 5.1}ような系列となります。

今回の問題は重みや系列の添字を整数に限った上でパーシステントホモロジーの $0$ 次部分を計算する問題と考えることができます。

入力

$G$ の頂点を $N$ 未満の各非負整数 $n$ で番号づけて頂点 $n$ と呼び、$G$ の辺を $M$ 未満の各非負整数 $m$ で番号づけて辺 $m$ と呼びます。

$M$ 未満の各非負整数 $m$ に対し、辺 $m$ の端点を頂点 $i_m$ と頂点 $j_m$ （$i_m, j_m$ は$i_m < j_m$ を満たす $N$ 未満の非負整数）と置き、辺 $m$ の重みを $w_m$ と置きます。

$T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力 $R$ を $R_t$ と置きます。

この時、入力は以下の形式で標準入力から $3 + M$ 行で与えられます：

• $1$ 行目に $N, M$ が半角空白区切りで与えられます。
• $M$ 未満の各非負整数 $m$ に対し、$2 + m$ 行目に $i_m, j_m, w_m$ が半角空白区切りで与えられます。
• $2 + M$ 行目に $T$ が与えられます。
• $3 + M$ 行目に $T$ 以下の各正整数 $t$ に対する $R_t$ が $t$ の小さい順に半角空白区切りで与えられます。

$N$ $M$
$i_0$ $j_0$ $w_0$
$\vdots$
$i_{M-1}$ $j_{M-1}$ $w_{M-1}$
$T$
$R_1$ $\cdots$ $R_T$

制約

入力は以下の制約を満たします：

• $N$ は $0 \leq N \leq 10^5$ を満たす整数
• $M$ は $0 \leq M \leq \min \{\frac{1}{2}N(N-1),10^5\}$ を満たす整数
• $M$ 未満の各非負整数 $m$ に対し、
• $i_m$ と $j_m$ は $0 \leq i_m < j_m < N$ を満たす整数
• $w_m$ は $1 \leq w_m \leq 10^5$ を満たす整数
• $T$ は $1 \leq T \leq 10^5$ を満たす整数
• $T$ 以下の任意の正整数 $t$ に対し、$R_t$ は $0 \leq R_t \leq 10^5$ を満たす整数

出力

$T$ 以下の各正整数 $t$ に対し、$t$ 行目に $t$ 個目の問題に対する答えを出力してください。

最後に改行してください。

サンプル

2 1
0 1 1
1
2

1

2 1
0 1 2
1
1

2

2 1
0 1 1
3
2 0 1

1
2
1

出典

1. J.-C. Hausmann, On the Vietoris--Rips Complexes and a Cohomology Theory for Metric Spaces, Ann. of Math. Stud., 138, Prospects in topology, pp. 175--188, 1995.