Problem Statement

At the beginning of the input, you are given a non-negative integer $N$, a non-negative integer $M$, and a weighted undirected graph $G$ with $N$ vertices and $M$ edges (without self-loops or multiple edges).

Consider the following problem.

A non-negative integer $R$ is given in the input.

Find the number of connected components of the weighted undirected graph obtained from $G$ by deleting the edges whose weight is greater than $R$. (Hereafter, this value is called the answer to this problem.)

A positive integer $T$ is given in the input. Answer $T$ such problems.

Background

In the field of Topological Data Analysis, a graded invariant called persistent homology is defined for weighted undirected graphs and is widely applied. For each fixed degree, persistent homology gives sequence data, indexed by non-negative real numbers, of geometric invariants called simplicial homology, and the sequence data formed by it and by its dual invariants are sequences that approximate other geometric invariants in a certain sense^{[1] Theorem 3.5, Theorem 5.1}.

This problem can be regarded as the problem of computing the degree-$0$ part of persistent homology, with the weights and the sequence indices restricted to integers.

Input

The vertices of $G$ are numbered by the non-negative integers $n$ less than $N$ and are called vertex $n$, and the edges of $G$ are numbered by the non-negative integers $m$ less than $M$ and are called edge $m$.

For each non-negative integer $m$ less than $M$, let vertex $i_m$ and vertex $j_m$ be the endpoints of edge $m$ (where $i_m, j_m$ are non-negative integers less than $N$ satisfying $i_m < j_m$), and let $w_m$ be the weight of edge $m$.

For each positive integer $t$ not exceeding $T$, let $R_t$ be the input $R$ for the $t$-th problem.

The input is then given from standard input in $3 + M$ lines in the following format:

• Line $1$ contains $N, M$, separated by a single-byte space.
• For each non-negative integer $m$ less than $M$, line $2 + m$ contains $i_m, j_m, w_m$, separated by single-byte spaces.
• Line $2 + M$ contains $T$.
• Line $3 + M$ contains $R_t$ for each positive integer $t$ not exceeding $T$, in increasing order of $t$, separated by single-byte spaces.

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

Constraints

The input satisfies the following constraints:

• $N$ is an integer satisfying $0 \leq N \leq 10^5$
• $M$ is an integer satisfying $0 \leq M \leq \min \{\frac{1}{2}N(N-1),10^5\}$
• For each non-negative integer $m$ less than $M$,
• $i_m$ and $j_m$ are integers satisfying $0 \leq i_m < j_m < N$
• $w_m$ is an integer satisfying $1 \leq w_m \leq 10^5$
• $T$ is an integer satisfying $1 \leq T \leq 10^5$
• For any positive integer $t$ not exceeding $T$, $R_t$ is an integer satisfying $0 \leq R_t \leq 10^5$

Output

For each positive integer $t$ not exceeding $T$, print the answer to the $t$-th problem on line $t$.

Print a newline at the end.

Sample

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

Source

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.