AlgoLiga 2018

Antek i Basia postanowili niedawno, że oprócz wymyślania rozrywek umysłowych, część wolnego czasu będą spędzać na wolnym powietrzu.  Razem z kolegami i koleżankami będą teraz grać w paintball. Aby uniknąć problemów, dzieci postanowiły bardzo dokładnie określić reguły gry.

Rozgrywka odbywa się w terenie o kształcie prostokąta o określonych wymiarach. Dla ułatwienia opisu, wprowadźmy taki układ współrzędnych,  że południowy i zachodni bok pola gry zawierają się w osiach układu.  Na polu gry znajdują się przeszkody w postaci cienkich ścian. Zawodnicy dzielą się na dwie równoliczne grupy: "zieloną" i "czerwoną", a następnie każda drużyna, w tajemnicy przed drugą, wybiera jedną z dwóch strategii: "L" lub "R". Zawodnicy z drużyny "zielonej" zajmują wyznaczone różne pozycje w punktach kratowych w południowej połowie pola gry, a "czerwoni" w północnej. Podczas gry zawodnicy nie zmieniają swoich pozycji. Na planszy znajdują się również przeszkody w postaci ścian.

Gra składa się z serii rund. W kolejnej rundzie, każdy pozostający w grze zawodnik bierze na cel jednego z przeciwników, których widzi (czyli takiego, który nie jest zasłonięty przez ścianę ani przez innego zawodnika) zgodnie ze strategią przyjętą przez jego drużynę. Jeśli gracza obowiązuje strategia "L", to bierze on na cel pierwszego przeciwnika ze swojej lewej strony. Analogicznie, gdy gracz należy do drużyny, która wybrała strategię "R", musi wycelować w przeciwnika, który znajduje się najbardziej na prawo z jego punktu widzenia. Runda kończy się jednoczesnym oddaniem strzałów przez wszystkich "żywych" graczy. Każdy strzał jest celny, a trafieni zawodnicy odpadają z rozgrywki i opuszczają pole gry.

Rozgrywka kończy się, gdy po którejś rundzie, co najmniej jedna z drużyn straciła wszystkich graczy, albo gdy w ostatniej rundzie nie padł żaden strzał, bo pozostali w grze zawodnicy nie widzą się wzajemnie. 

Antek i Basia doszli do wniosku, że przy tak określonych zasadach gry i zakładając, że każda z drużyn niezależnie od siebie z jednakowym prawdopodobieństwem wybiera strategię "L" lub "R", właściwie nie trzeba w ogóle zaczynać rozgrywki. Można za to obliczyć wartości oczekiwane kilku parametrów dotyczących gry.

Wejście

W pierwszej liczba rozgrywek t (1 ≤ t ≤ 20).

Opis jednej rozgrywki przedstawia się nastepująco.

W pierwszej linii cztery liczby całkowite X, Y (1 ≤ X, Y ≤ 10000), G (1 ≤ G ≤ 100) i S (0 ≤ S ≤ 100), gdzie: X - wymiar planszy w kierunku wschód-zachód, Y - wymiar planszy w kierunku północ-południe, G - liczba graczy w każdej z drużyn, S - liczba ścian na planszy.

Następnie w G liniach po dwie liczby całkowite x_z i y_z oznacząjące pozycje kolejnych graczy drużyny "zielonej". W kolejnych G liniach po dwie liczby całkowite x_c i y_c oznaczające pozycje kolejnych graczy drużyny "czerwonej" (0 ≤ x_z, x_c ≤ X; 0 ≤ y_z < Y/2 < y_c ≤ Y).

W kolejnych S liniach po cztery liczby całkowite x₁, y₁, x₂, y₂ oznaczające współrzędne końców kolejnych ścian (0 ≤ x₁, x₂ ≤ X; 0 ≤ y₁, y₂ ≤ Y).

Wymiary zawodników i grubość ścian zaniedujemy, więc zawodników traktujemy jak punkty, a ściany jak odcinki.
Zagwarantowane jest, że każdy z graczy zajmuje wolny punkt na planszy (w szczególności nie przechodzi przez ten punkt żadna ze ścian).

Wyjście

Dla każdej rozgrywki w osobnej linii wyniki obliczeń w postaci "z-r-c gz:gc lr" gdzie:
z - wartość oczekiwana liczby zwycięstw "zielonych" po przeprowadzeniu czterech rozgrywek na tej samej planszy i przy takim samym rozmieszczeniu zawodników.
r - wartość oczekiwana liczby remisów (w takim samym czteromeczu jak wyżej).
c - wartość oczekiwana liczby zwycięstw "czerwonych" (w takim samym czteromeczu jak wyżej).
gz - wartość oczekiwana liczby zawodników drużyny "zielonej" pozostałych na planszy po zakończeniu gry, podana z dokładnością do dwóch miejsc po przecinku.
gc - wartość oczekiwana liczby zawodników drużyny "czerwonej" pozostałych na planszy po zakończeniu gry, podana z dokładnością do dwóch miejsc po przecinku.
lr - wartość oczekiwana liczby rozegranych rund, podana z dokładnością do dwóch miejsc po przecinku.

Przykład

Wejście:
3
8 8 4 3
0 0
7 2
8 1
0 3
0 6
4 7
8 7
7 6
7 4 6 1
3 1 7 1
5 2 6 0
12 10 3 4
2 2
9 2
5 0
2 9
8 9
7 6
1 3 1 5
8 7 9 8
1 5 3 6
2 5 1 6
8 10 2 1
0 2
6 1
6 8
3 6
4 6 2 9

Wyjście:
3-0-1 1.75:0.75 1.75
2-0-2 0.50:0.50 1.50
1-2-1 0.50:0.50 1.25

Wyjaśnienie do pierwszej rozgrywki z przykładu:

1. Jeśli zieloni wybrali strategię "L" a czerwoni "R", to gra kończy się po jednej rundzie zwycięstwem zielonych. Trafieni zostają wszyscy zawodnicy drużyny czerwonej i tylko jeden z zielonej.

2. Jeśli zieloni wybrali strategię "R" a czerwoni "L", to gra kończy się po dwóch rundach zwycięstwem czerwonych. W drugiej rundzie nie pada żaden strzał, bo pozostali w grze R1 i R2 nie widzą G2.

3. Jeśli obie drużyny wybiorą strategię "R", gra zakończy się po 3 rundach wynikiem 2:1 dla zielonych.

4. Jeśli obie drużyny wybiorą strategię "L", gra zakończy się po 1 rundzie. Na planszy pozostanie tylko zawodnik G2.