Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Năm nay, World Cup 2014 được tổ chức tại Brazil. Bốc thăm chia bảng cho các đội đã được thực hiện xong từ tháng 12 năm ngoái. Bây giờ, chúng ta quay lại tháng 12 của năm trước, để xem xét các trường hợp có thể xảy ra cho việc chia bảng đấu World Cup.

Công việc bốc thăm chia bảng có một số yêu cầu như sau:

1) Có g bảng đấu, mỗi bảng có m đội.

2) Có g đội hạt giống, gồm đội chủ nhà, và g-1 đội khác đã được chọn trước, dựa vào kết quả của vòng loại.

3) Các đội còn lại được chia thành m-1 nhóm, mỗi nhóm có g đội.  Mỗi đội chỉ nằm trong 1 nhóm duy nhất.

4) Trong cùng 1 bảng, không có 2 đội nào đến từ cùng một châu lục. Nếu châu lục nào có hơn g đội tham gia, thì có thể bỏ qua điều kiện này.

5) Với châu lục có <= g đội tham gia, sẽ không có nhóm nào có cả g đội đến từ châu lục này.

Bảng xếp hạng FIFA luôn được cập nhật, các chuyên gia bóng đá dựa vào đây để đánh giá sức mạnh cho từng đội. Yêu cầu: Hãy tìm tổng sức mạnh trung bình của các đối thủ còn lại trong bảng của đội bóng t cho trước.

Input

Dòng đầu tiên là số lượng bộ test T (T <= 10). Mỗi bộ test gồm:

Dòng đầu tiên gồm 2 số nguyên g <= 8 và m <= 4, là số bảng đấu và số đội cho mỗi bảng.

Tiếp theo là g*m số nguyên. Số thứ i là s_i (0 <= s_i <= 10000) là sức mạnh của đội thứ i-1 (đánh số đội bắt đầu từ 0). Đội 0 là đội chủ nhà.

Dòng tiếp theo gồm g-1 số, là các đội được xếp vào nhóm hạt giống cùng đội chủ nhà.

Sau đó là số nguyên c, là số châu lục có đội bóng tham gia. c dòng tiếp theo, số đầu tiên là n_i, số đội bóng trong vùng châu lục đó. Theo sau là n_i đội thuộc châu lục này.

Dòng cuối cùng chứa số nguyên t, là đội mà chúng ta cần xem xét.

Output

Với mỗi test, in ra một số tổng sức mạnh trung bình của các đối thủ còn lại trong bảng của đội t, độ chính xác 10^-3.

Example

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

Output:
6.000
6.500


Giải thích test 1 (thứ tự bảng không quan trọng nên có thể bỏ qua):
Có 2 đội hạt giống là đội chủ nhà, đội 0, và đội số 1. Nhóm hạt giống thứ 2 gồm đội 2 và đội 5, 
nhóm thứ 3 gồm đội 3 và đội 4. Tất cả các đội đều đến từ 1 quốc gia, do đó có 4 khả năng xảy ra:
(1) Bảng 1 có các đội 0-2-3, bảng 2 có các đội 1-5-4. Tổng sức mạnh các đối thủ của đội 5 là 7.
(2) Bảng 1 có các đội 0-5-3, bảng 2 có các đội 1-2-4. Tổng sức mạnh các đối thủ của đội 5 là 5.
(3) Bảng 1 có các đội 0-2-4, bảng 2 có các đội 1-5-3. Tổng sức mạnh các đối thủ của đội 5 là 6.
(4) Bảng 1 có các đội 0-5-4, bảng 2 có các đội 1-2-3. Tổng sức mạnh các đối thủ của đội 5 là 6.
Trung bình tổng sức mạnh các đối thủ của đội 5 bằng 6.

Giải thích test 2:
Đội 0 và đội 5 ở cùng một châu lục, do đó phải ở 2 bảng khác nhau, và chỉ còn có 2 khả năng là:
(1) Bảng 1 có các đội 0-2-3, bảng 2 có các đội 1-5-4. Tổng sức mạnh các đối thủ của đội 5 là 7.
(2) Bảng 1 có các đội 0-2-4, bảng 2 có các đội 1-5-3. Tổng sức mạnh các đối thủ của đội 5 là 6.
Trung bình tổng sức mạnh các đối thủ của đội 5 bằng 6.5.