Minimum Cut Query Counting

In this problem, you are given an undirected weighted graph. A partition of the vertex set into two disjoint subsets is called an s–t cut if two specified vertices s and t lie in different subsets. For a weighted graph, the capacity of a cut is defined as the sum of the weights of all edges that cross the two parts. In particular, the s–t minimum cut is defined as:

$\min\{\mbox{capacity}(C) : C \mbox{ is an } s–t \mbox{ cut}\}$

Now, you are given an undirected weighted graph. There are several queries of the form "How many unordered pairs of vertices have an s–t minimum cut capacity no more than x?"

Your task is to answer these queries.

inputFormat

The first line contains three integers n, m and q where n is the number of vertices, m is the number of edges, and q is the number of queries.

Then, m lines follow. Each of these lines contains three integers u, v, w indicating an undirected edge between vertices u and v with weight w.

After that, there are q lines, each containing a single integer x representing a query.

outputFormat

For each query, output one line containing a single integer – the number of unordered vertex pairs whose s–t minimum cut capacity is less than or equal to x.

sample

4 3 3
1 2 3
2 3 2
3 4 4
2
3
4

4
5
6