Network Planning

In petroleum retail, where a company puts its service stations decides how much it earns. To choose the sites for new stations, the company runs a procedure it calls network planning.

You are a consultant for this company. It hands you the number of cities and the roads between them, the fuel demand of every city, the list of cities that already have a service station, and the number of new stations it must build this year. What it wants back is the set of cities that should get the new stations so that the total supply is as large as possible.

The rules:

• There are $N$ cities, and a city holds at most one service station.
• A service station can supply any amount of fuel, with no upper limit.
• A service station supplies 70% of the demand of its own city, plus another 10% of the demand of each neighboring city. That holds whether or not a neighboring city has a station of its own.
• For example, if cities A, B, and C are all neighbors of each other and A and B have stations, the station in A supplies 70% of A's demand, 10% of B's demand, and 10% of C's demand. The station in B supplies the same way.
• The terrain limits a city to at most three neighbors.
• Total revenue is directly proportional to the total fuel supplied.

The first line contains the number of test cases $T$ ($T \le 10$).

Each test case begins with a line containing the number of cities $N$ ($1 \le N \le 100000$).

The next $N$ lines contain the fuel demand $D_i$ of city $i$ in liters, one per line ($0 \le D_i \le 1000$).

The next line contains the number of roads $E$.

Each of the next $E$ lines contains two city numbers $C_1$ and $C_2$ that are neighbors. Roads are bidirectional and no road is listed twice, so if $(C_1, C_2)$ appears then $(C_2, C_1)$ does not appear in the same test case. Cities are numbered 1 through $N$. Since a city has at most three neighbors, $E \le \lfloor 3N/2 \rfloor$.

The next line contains the number of cities that already have a service station, $S$ ($0 \le S < N$).

Each of the next $S$ lines contains one such city number.

The last line contains the number of new stations to build this year, $M$ ($1 \le M \le N - S$). Exactly $M$ stations must be built.

Print two lines for each test case.

The first line holds the largest total fuel supply the company can reach, counting the existing stations together with the new ones, printed as an integer. The total is always a multiple of 0.1 liters, so round it to the nearest integer, and round up when the fractional part is exactly 0.5.

The second line lists the cities that get the new stations, in increasing order, separated by single spaces. Cities that already have a station never appear in this list. When several choices reach that largest total, print the one that comes first in lexicographic order once each choice is written in increasing order.

The first example holds two test cases. In the first of them, building the single new station in city 3 brings the total supply to 360 liters, which is the largest possible.

The second one has two optimal answers. Building in cities 1, 2, and 5 supplies exactly as much as building in cities 1, 3, and 5, so the answer is 1 2 5 because it comes first in lexicographic order. City 1 then supplies 268.2 liters, city 2 supplies 182.6, and city 5 supplies 290, while city 4, which already had a station, supplies 150. The sum is 268.2 + 182.6 + 290 + 150 = 890.8, printed as 891 after rounding.