IX Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 11.06.2005

Opis

Zły władca Patentolandii planuje zmasowany atak w celu podporządkowania sobie wolnej Bajtocji. Na szczęście bajtockiemu wywiadowi udało się dojść do kanału przez który przesyłane są wszystkie tajne rozkazy wydawane odziałom Patentolandii, dzięki czemu istnieje szansa ocalenia Bajtocji. Okazało się jednak, że wszystkie wiadomości są kodowane nieznanym wcześniej szyfrem. Na szczęście grupie kryptologów udało się w porę go złamać - stwierdzono, że do zdekodowania pojedynczej wiadomości potrzebna jest pewna liczba-klucz D.

Odkryto, że Patentolandczycy wyznaczają ją z pewnego ciągu c_1..N w następujący sposób:
D = d_N
gdzie
d₁ = c₁
d_i = (48271d_i-1 + c_i) mod 2³²   dla i=2..N

Kryptolodzy ustalili, że stosowany ciąg c_1..N jest w rzeczywistości najmniejszą leksykograficznie permutacją liczb 1..N spełniającą warunek a_i≤c_i≤b_i, gdzie a_1..N i b_1..N obliczane są w następujący sposób:
a₁ = 1
a_i = a_i-1 + (P_2i-2 mod (i-a_i-1+1))  dla i=2..N
b_i = a_i + (P_2i-1 mod (N-a_i+1)       dla i=1..N
gdzie
P_i+1 = (kP_i + l) mod m

W przypadku, gdy nie istnieje permutacja spełniająca powyższe warunki, Patentolandczycy używają jako klucza D liczby 666.

Tobie, jako nadwornemu programiście, zostało przydzielone zadanie polegające na napisaniu programu wyznaczającego niezbędne klucze. Pamiętaj, że od Twojego programu zależy przyszłość Bajtocji...

Wejście

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita oznaczająca liczbę wiadomości do deszyfracji.

W pierwszej i jedynej linii opisującej pojedynczą wiadomość znajduje się pięć liczb całkowitych (N, P₁, k, l oraz m) spełniających następujące ograniczenia:
1 ≤ N ≤ 500000
0 ≤ P₁, k, l < 2³²
1 ≤ m < 2³²

Wyjście

Dla każdej wiadomości należy wypisać dokładnie jedną linię zawierającą klucz D służący do jej deszyfracji.

Przykładowe wejście

1
3 0 1 1 10

Przykładowe wyjście

2330185986