Robotron

Î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ță

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 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 \leq N \leq 10^5$; $1 \leq L \leq 10^9$; $1 \leq K \leq 10^9$;
• $101 \leq E_i < 10^9$; $1 \leq P_i \leq 10^6$; $1 \leq CP \leq 99$.

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 $\textbf{3}$ (jucătorii cu codurile $31$, $32$, $33$, $30$) și $\textbf{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 $\textbf{3}$ are următorii jucători, cu codurile și puterile aferente: ${\color{red}31} \ 5$, ${\color{red}32} \ 2$, ${\color{red}33} \ 5$, ${\color{red}30} \ 3$

Echipa planetei cu codul $\textbf{45}$ are următorii jucători, cu codurile și puterile aferente: ${\color{blue}21} \ 5$, ${\color{blue}22} \ 6$, ${\color{blue}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 $\textbf{3}$: ${\color{red}32} \ 2$, ${\color{red}33} \ 5$, ${\color{red}30} \ 3$, ${\color{red}31} \ 5$

Echipa planetei cu codul $\textbf{45}$: ${\color{blue}22} \ 6$, ${\color{blue}23} \ 1$, ${\color{blue}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.