Fall FLASG | Bricodeque

Primul venit, primul servit.

Te afli în magazinul Bricodeque. Acest magazin își dorește un număr cât mai mare de clienți care vor achita produse. Pe lângă asta, mai dorește ca fiecare client să stea cât mai puțin la rândul casei de marcat.

De azi, magazinul dorește să introducă noul algoritm de sortare a clienților la casele de marcat, doar că dă rateuri și ești rugat să faci un alt cod.

Ți se oferă pentru ziua de azi numărul de clienți pe care o să aibă magazinul, un număr $N$, respectiv momentul în care fiecare client va ajunge în zona caselor de marcat. Magazinul are $K$ case de marcat. Fiecare casă de marcat are o limită $LIM$ de persoane care pot sta la rând până când clientul din față va plăti. Dacă o casă de marcat este plină, aceasta este considerată închisă până când persoana din față va plăti. Dacă toate casele de marcat sunt închise, atunci clientul va pleca la un alt magazin. Acest lucru nu ne convine, astfel va trebui să facem tot posibilul de a avea câți mai puțini clienți care pleacă din magazin.

Fiecare client va sta la rând un timp $T$ de secunde până când va achita. Dacă în fața lui se află $P$ persoane, va aștepta până când îi va urma rândul la casă. Doar când acesta va fi primul la rând se vor porni cele $T$ secunde.

Date de intrare

Pe prima linie se află $4$ numere $N$, $K$, $T$ și $LIM$, cu semnificația de mai sus.
Apoi va urma $N$ linii, unde pentru fiecare client $i$, $i=\overline{1,N}$ se află timpul la care acesta ajunge în zona caselor de marcat.

Date de ieșire

Pe prima linie se vor găsi $2$ numere, primul fiind numărul maxim de clienți care au plătit, respectiv timpul la care ultimul client a ieșit de la rând.
Pe următoarele $N$ linii se vor găsi $2$ numere, indexul clientului în ordinea dată, respectiv casa de marcat unde acesta s-a pus la rând. Dacă toate casele de marcat sunt închise, se va afișa -1.

Restricții și precizări

• $N \leq 100 \ 000$
• $K \leq 1 \ 000$
• $LIM \leq 100$
• $T \leq 100$
• timpul la care un client ajunge la zona caselor de marcat $\leq 1 \ 000$
• Dacă există mai mulți clienți care ajung în același timp la casele de marcat, prioritate va avea cel care are indexul mai mic la citire.
• Dacă un client $X$ poate intra doar la o casă de marcat, iar clientul din față iese tot în același moment, atunci clientul $X$ se poate pune la rând.

Exemplul 1

stdin

10 2 3 2
1
1
1
2
3
3
4
5
5
7

stdout

7 13
1 1
2 2
3 1
4 2
5 -1
6 -1
7 1
8 2
9 -1
10 1