Gra w dzielniki
Limit pamięci: 256 MB
Jak zapewne wszyscy pamiętają, Bajtuś i Bituś to dwaj chłopcy, którzy lubią grać w rozmaite gry.
Ostatnio Bituś poniósł porażkę, zjadając oznaczony kawałek czekolady i chce się zrewanżować Bajtusiowi.
Zaproponował mu nową grę, jej zasady są następujące.
Początkowo na tablicy napisana jest pewna liczba całkowita większa od .
Gracze na przemian zastępują liczbę aktualnie napisaną na tablicy jej wybranym dzielnikiem (różnym od niej samej).
Gdy któryś z graczy napisze liczbę , gra się kończy.
Dla każdego dzielnika liczby , z wyjątkiem , określone są dwie liczby i .
Gdy Bajtuś w trakcie gry napisze na tablicy liczbę , dostaje punktów.
Z kolei Bituś, za napisanie otrzymuje punktów.
Celem gry jest zmaksymalizowanie przewagi nad przeciwnikiem, czyli różnicy między zdobytymi punktami a punktami przeciwnika.
Bituś wybrał już liczbę oraz punktację dla jej dzielników.
Za to Bajtuś może wybrać, który z chłopców wykona pierwszy ruch.
Chciałby on wobec tego wiedzieć, ile w obydwu przypadkach wyniesie przewaga rozpoczynającego grę, przy założeniu, że obaj chłopcy grają optymalnie.
Wejście
Pierwszy wiersz wejścia zawiera dodatnią liczbę całkowitą oznaczającą liczbę przypadków testowych, które są kolejno opisane w dalszej części wejścia.
Opis jednego przypadku testowego rozpoczyna się wierszem z czterema liczbami całkowitymi i (, ).
Iloczyn jest równy liczbie , która początkowo znajduje się na tablicy, zaś oznacza liczbę dodatnich dzielników liczby .
W dalszych wierszach znajduje się punktacja dla kolejnych (różnych od ) dzielników , w kolejności rosnącej.
W -tym z tych wierszy znajdują się dwie liczby całkowite oraz (), które oznaczają liczbę punktów przyznawanych odpowiednio Bajtusiowi i Bitusiowi za napisanie na tablicy liczby , czyli -tego dzielnika .
Suma liczb po wszystkich przypadkach testowych w jednym pliku nie przekracza .
Wyjście
Wypisz wierszy z odpowiedziami dla poszczególnych przypadków testowych.
Odpowiedź dla jednego przypadku składa się z dwóch liczb całkowitych i , które oznaczają przewagę rozpoczynającego grę, jeśli jest nim, odpowiednio, Bajtuś i Bituś.
Przykład
Dla danych wejściowych:
2
7 1 1 2
3 1
2 2 1 3
1 1
3 3
poprawną odpowiedzią jest:
3 1
2 2
Wyjaśnienie: W pierwszym przypadku testowym rozpoczynający grę może napisać jedynie , co od razu kończy grę.
W drugim zaś opłaca się napisać i pozwolić przeciwnikowi napisać .
Autor zadania: Tomasz Kociumaka.