Problem A: Generator

Treść

Franek jest hakerem jakich mało. Nie raz już pokazał co jest wart, wykrywając luki w zabezpieczeniach stron internetowych, baz danych, czy w protokołach przesyłania informacji, które do tej pory były uznawane za całkowicie bezpieczne. Jego ambicją jest utworzenie takiego sposobu szyfrowania danych, który z założenia będzie odporny na wszelkie próby złamania. Franek wie, że kluczową rolę pełni tu jakość generatora liczb losowych. W pierwszym odruchu chciał użyć szeroko stosowanego liniowego generatora kongruencyjnego, którego schemat działania można opisać wzorem:

dla którego przy zadanych całkowitych współczynnikach m, a, c, x₀ można w łatwy sposób obliczyć kolejne wartości x_i. Niestety taki generator ma pewną wadę. Otóż dla zadanej wartości x_i wartość x_{i + 1} będzie zawsze taka sama. Oznacza to, że jeżeli potencjalny włamywacz dysponuje odpowiednio dużą bazą historycznych wyników generatora, w łatwy sposób może przewidzieć kolejną obliczoną przez generator liczbę. Dlatego też Franek postanowił wprowadzić małą modyfikację. Jego generator jest złożeniem kilku różnych generatorów liniowych, według następującego wzoru:

Teraz Franek chciałby tak dobrać współczynniki swojego generatora, by otrzymywane wartości powtarzały się jak najrzadziej, inaczej mówiąc, by rozkład wyników był jak najbardziej zbliżony do rozkładu jednostajnego. Napisz program, który umożliwi przeprowadzenie niezbędnych testów i dla zadanych współczynników m_j, a_j, c_j, y_j,0, M oraz liczby wywołań generatora wyznaczy wartość, która jest generowana najczęściej, oraz liczbę jej powtórzeń.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera liczbę całkowitą g (1<=g<=10) oznaczającą liczbę generatorów liniowych wchodzących w skład generatora Franka. W kolejnych g wierszach podane są liczby całkowite m_j, a_j, c_j, y_j,0 (2<=m_j<=2³², 0<a_j<m_j, 0<=c_j<m_j, 0<=y_j,0<m_j), oddzielone pojedynczymi spacjami, reprezentujące współczynniki j-tego generatora liniowego. Ostatnia linia zestawu danych składa się z dwóch liczb całkowitych M, n (2<=M<=2³², 1<=n<=2 000 000), oddzielonych spacją, oznaczającymi odpowiednio współczynnik M generatora Franka oraz liczbę wywołań podczas testu.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu są dwie liczby całkowicie oddzielone spacją, oznaczające kolejno najczęściej generowaną wartość oraz liczbę jej wystąpień. W przypadku gdy kilka wartości powtarza się jednakową (maksymalną) liczbę razy, należy podać najmniejszą z nich.

Przykład

dane wejściowe:
2
1
4 1 1 2
4 9
2
16 5 7 1
32 7 17 6
12 20

wynik:
3 3
1 5