Cheating or Not

Time limit1sMemory limit128 MB

Summary

Given g groups, seeded teams, pots, and confederation constraints, compute the average total strength of a given team's group opponents over all valid draws.

Level: Hard9 of 10
Topics: Combinatorics, Probability, Math, Brute force
Solved: No attempts yet

Problem

For the organizers of a soccer world championship, the final draw is a very delicate job. It determines the composition of the groups for the first stage of the tournament, and indirectly the possible matches in the knockout stage too. Its importance lies in the fact that a team's success may depend on the opponents it faces — and perhaps even the winner of the tournament.

The final draw is often the target of fraud accusations. Some teams feel their group is stronger than the others and complain that they were cheated. Your job is to provide facts that can help convince them otherwise.

The draw is somewhat complicated by several fairness considerations. The goal is to avoid assigning too many strong teams to the same group, and teams from different confederations should be spread across groups. This is ensured by the following rules.

There are $g$ groups with $m$ members each.
The hosting nation is seeded first in the first group.
$g - 1$ selected teams are seeded first in the remaining groups.
The remaining positions are drawn from $m - 1$ pots, one team from each pot per group.
You are told which teams belong to the same confederation, and you must ensure that no two teams of the same confederation share a group. For a confederation with more than $g$ teams this is impossible, so for such a confederation this rule is ignored.
You may assume that for a confederation with at most $g$ teams, all of its teams that are not seeded lie in the same pot.
Each team belongs to exactly one confederation, and each team is either seeded or contained in exactly one pot.

We want to compute the average strength of the opponents of a given team — that is, the average of the sum of the strengths of the other teams in that team's group. The strengths of the teams are given in the input. The average is taken over all valid draws, which are assumed to be equally likely.

Input

The input starts with the number of test cases. Each test case is described as follows.

The first line contains the number of groups $g \le 8$ and the number of teams per group $m \le 4$ .

The next line contains $g \cdot m$ integers; the $i$ -th integer $0 \le s_i \le 10\,000$ is the strength of team $i$ . Team indices start at $0$ , and by convention the hosting nation is team $0$ .

The next line lists the $g - 1$ seeded teams by their numbers. Each of the following $m - 1$ lines contains $g$ team numbers that are allocated to the same pot.

The next line contains the number of confederations $c$ . Each of the following $c$ lines describes one confederation: it begins with the number of teams $n_i > 0$ , followed by the $n_i$ team indices.

The last line contains the number $t$ of the team whose average group strength must be evaluated.

Output

For each test case, output on a single line the average of the sum of the strengths of team $t$ 's opponents in the group stage, rounded to three decimal places.

Examples1

Example 1

Input

2
2 3
1 2 3 4 5 6
1
2 5
3 4
1
6 0 1 2 3 4 5
5
2 3
1 2 3 4 5 6
1
2 5
3 4
2
2 0 5
4 1 2 3 4
5

Expected output

6.000
6.500