În sistemul solar Stelarion sunt 99 de planete. Planeta Hazard găzduiește campionatul de Robotron pe echipe. Jucătorii sunt înregistrați în ordinea sosirii lor, indiferent de planeta de pe care provin. Anul acesta s-au înscris în campionat N jucători de pe M planete. Jucătorul înregistrat al i-lea (cu i de la 1 la N) primește două numere: E[i] — numărul trecut pe ecuson și P[i] — puterea jucătorului. Numărul trecut pe ecuson este format din codul planetei jucătorului CP (numărul format din ultimele două cifre de pe ecuson) și codul jucătorului CJ (numărul format din restul cifrelor). Jucătorii care reprezintă aceeași planetă vor fi repartizați în aceeași echipă, poziția pe care o ocupă inițial în echipă fiind în ordinea înregistrării lor în concurs. În cadrul campionatului se vor disputa mai multe runde, iar la fiecare rundă va fi desemnată o echipă câștigătoare.

Regulamentul de concurs:

• O rundă constă în parcurgerea unui circuit format din L căsuțe, numerotate de la 1 la L, în sens orar, plasate ca în figură.
• Fiecare echipă dispune de un pion care este plasat în căsuța 1 la începutul fiecărei runde; o mutare a jucătorului al i-lea în ordinea înregistrării constă în deplasarea pionului echipei proprii cu P[i] căsuțe, în sens orar.
• În fiecare rundă, echipele joacă ciclic, în secvențe succesive, fiecare secvență fiind în ordinea strict crescătoare a codurilor planetelor de pe care provin. Într-o secvență joacă toate echipele, doar ultima secvență a rundei putând fi incompletă, după caz. Ordinea echipelor nu se schimbă de la o rundă la alta. Când este rândul unei echipe să joace, unul dintre membrii acesteia mută pionul echipei respective.

• La prima rundă, în cadrul fiecărei echipe, jucătorii ocupă pozițiile inițiale, stabilite la înscriere. Pentru fiecare altă rundă care urmează, în fiecare echipă, se schimbă poziția jucătorilor, aceștia permutându-se circular. Astfel cel care a fost primul la runda anterioară devine ultimul, iar cel care fusese al doilea va fi acum pe prima poziție.
• La fiecare rundă, în cadrul fiecărei echipe, jucătorii mută pionul echipei pe rând, în ordinea poziției pe care o ocupă în echipă în runda respectivă. După jucătorul care ocupă ultima poziție în echipă la runda curentă va muta jucătorul care ocupă prima poziție.
• Runda se încheie când pionul uneia dintre echipe a parcurs tot circuitul, ajungând din nou la poziția 1 sau trecând peste aceasta. Această echipă este desemnată ca fiind echipa câștigătoare a rundei, iar jucătorul care aduce victoria echipei sale este cel care face ultima mutare, de tipul precizat.

Cerința

1) Să se determine numărul M al echipelor participante și codul H al planetei gazdă Hazard, știind că numărul jucătorilor din echipa planetei gazdă este strict mai mare decât numărul jucătorilor oricărei alte echipe.

2) Să se determine codul planetei de pe care provine echipa câștigătoare la runda K și codul jucătorului care aduce victoria acestei echipei la aceasta rundă.

Date de intrare

Fișierul de intrare robotron.in conține pe prima linie un număr C, reprezentând numărul cerinței, pe a doua linie, 3 numere naturale N, L și K cu semnificația din enunț. Pe următoarele N linii sunt datele jucătorilor: pe a i-a dintre aceste linii se află câte două numere naturale E[i] și P[i], cu semnificația din enunț. Numerele de pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire robotron.out va conține pe prima linie, pentru C=1, numerele M și H, iar pentru C=2, codul planetei și al jucătorului precizate la cerința 2. Numerele de pe aceeași linie a fișierului sunt despărțite printr-un spațiu.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ L ≤ 1.000.000.000
• 1 ≤ K ≤ 1.000.000.000
• 101 ≤ E[i] ≤ 1.000.000.000
• 101 ≤ P[i] ≤ 1.000.000
• 1 ≤ CP ≤ 99
• Pentru 20 de puncte, C = 1, N ≤ 1000
• Pentru 30 de puncte, C = 1
• Pentru 10 puncte, C = 2, N ≤ 10000, L ≤ 10000, K ≤ 1000
• Pentru 10 puncte, C = 2, N ≤ 10000, L ≤ 10000
• Pentru 30 de puncte, C = 2

Exemplul 1:

robotron.in

1
7 23 2
245 5
3103 5
3203 2
3303 5
2245 6
3003 3
231745 1

robotron.out

2 3

Explicație

Sunt 7 jucători și ei vor fi împărțiți în 2 echipe (M = 2), reprezentând planetele cu codurile 3 (jucătorii cu codurile 31, 32, 33, 30) și 45 (jucătorii cu codurile 2, 22, 2317). Codul planetei gazdă Hazard este H = 3, echipa planetei 3 fiind cea mai numeroasă.

Exemplul 2:

robotron.in

2
7 23 2
2145 5
3103 5
3203 2
3303 5
2245 6
3003 3
2345 1

robotron.out

45 21

Explicație

Traseul conține 23 de căsuțe, iar la prima rundă membrii echipelor au pozițiile stabilite la înscriere și vor muta în ordinea acestor poziții:

Echipa planetei cu codul 3 are următorii jucători, cu codurile și puterile aferente: 31 5, 32 2, 33 5, 30 3

Echipa planetei cu codul 45 are următorii jucători, cu codurile și puterile aferente: 21 5, 22 6, 23 1.

La runda a 2-a pozițiile membrilor se schimbă, primii jucători din fiecare echipă trecând la coadă:

Echipa planetei cu codul 3: 32 2, 33 5, 30 3, 31 5.

Echipa planetei cu codul 45: 22 6, 23 1, 21 5.

Echipa planetei cu codul 45 termină jocul în runda a 2-a după 6 mutări, care, pentru această echipă, vor fi efectuate în ordine de jucătorii 22, 23, 21, 22, 23 si 21. Deci ultima mutare o va face jucătorul cu codul CJ = 21, care ajunge în căsuța 2, deci trece peste căsuța 1. Ordinea în care mută jucătorii celor două echipe în cadrul acestei runde, precum și numerele căsuțelor ocupate succesiv de cei doi pioni, sunt ilustrate în tabelul de mai jos.