Giải bài trực tuyến

You are given a weighted undirected graph with edge weight denoting the capacity of the edge.

Now given a number x, output how many unordered (s,t) pairs are there in the graph such that minCut(s,t) <= x.

A Cut is a partition of the vertices of a graph into two sets such that s and t belong to different set after the partition.

In weighted graphs, the size of a cut is defined to be the sum of weights of the edges crossing the cut. minCut is a cut whose size is the least possible.

Input

First line contains T, the number of test cases.

For each test case the first line contains two integers n and m, denoting the number of vertices and the number of edges in the graph.

Next m lines contain 3 integers u,v,c denoting an undirected of capacity c between vertices u and v; 1 <= u,v <= n.

Next line contains q, the number of queries. Next q line contains one number each which denotes the input x for ith query.

Note: there can be multiple edges between a pair of vertices.

Output

The output for each test case should consist of q lines with one integers in each of them denoting the number of unordered (s,t) pairs corresponding to that query. Output a blank line BETWEEN the test cases.

Note: The timelimit for the problem is somewhat strict.

Example

Input:
1
5 0
1
0

Output:
10

Constraints

Input Set 1: numberOfTestCases <= 15, n <= 40, m <= 400, q <= 10

Input Set 2: numberOfTestCases <= 20, n <= 150, m <= 3000, q <= 30

Edge weights are less than or equal to 10^6