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

You are given an unweighted undirected graph G. Each vertex has a positive weighted associated with it. Weight of a set of vertices is defined as the sum of weights of all vertices in the set.

A set of vertices is called independent if there is no edge in the graph with both endpoints on vertices of this set.

A subgraph induced by a set of vertices is a graph with vertex set as the given set of vertices and edges in the original graph with both endpoints in the given set.

If s denotes a set of vertices, then Query(s, G) = Maximal weighted independent set in the subgraph induced by s.

Given q queries and the description of the graph, you are to output the weight of the Maximal weighted independent set corresponding to each of the queries.

Input

First line contains T, the number of test cases.

Each test case description starts with one line containing 2 integers n and m, denoting the number of vertices and number of edges.

Next line contains n space separated integers denoting the weight of vertices from 0 to n - 1 ( inclusive ).

Next m lines contains two integers u and v (u != v, 0 ≤ u, v < n), denoting an undirected edge from u to v.

Next line contains q, the number of queries.

Next q lines contain description of a query. Description of a query starts with an integer denoting the size of set s, followed by the vertices which are members of vertex set s.

Output

For each test case, output q lines containing the answer to each query. Print a blank line BETWEEN the output of multiple test cases.

Example

Input:
2
5 1
1 2 3 4 5
0 1
3
3 0 1 2
3 1 2 3
2 0 1
3 3
1 2 3
0 1
0 2
1 2
1
3 0 1 2

Output:
5
9
2

3 

Constraints

Dataset 1: T ≤ 20, n ≤ 30 , m ≤ 1000, q ≤ 1000 , weight_of_a_vertex ≤ 1000 Time limit: 5s

Dataset 2: T ≤ 10, n ≤ 40, m ≤ 1000, q ≤ 100, weight_of_a_vertex ≤ 1000 Time limit: 5s