cursa

O cursă de maşini electrice prevăzute cu panouri solare are loc pe un traseu care traversează $n$ localităţi, numerotate în ordinea de pe traseu de la $1$ la $n$. Linia de start se află la kilometrul zero şi coincide cu începutul primei localităţi. Linia de sosire este la sfârşitul ultimei localităţi. Orice localitate, exceptând localitatea $1$, începe la sfârşitul localităţii precedente. Prin urmare, pentru fiecare localitate i se cunoaşte distanţa $d_i$ de la linia de start până la sfârşitul localităţii, exprimată în $\text{km}$.
În momentul începerii competiţiei, din fiecare localitate există exact o maşină aliniată la linia de start. Maşinile au aceleaşi caracteristici, ca urmare se deplasează cu aceeaşi viteză, cu excepţia traversării localităţii din care provin unde, datorită avantajelor terenului propriu (suporteri dotaţi cu oglinzi, lămpi, etc.), îşi dublează instantaneu viteza până la ieşirea din localitate, apoi revin la viteza iniţială.
La concurs sunt invitate şi televiziunile locale, iar pentru telespectatori, sarea şi piperul sunt depăşirile, de aceea este important să reţinem informaţii despre acestea, pentru a le putea viziona în reluare. Se consideră depăşire situaţia în care o maşină ajunge din urmă o altă maşină, apoi trece în faţa acesteia.

Cerinţă

Cunoscând localităţile de pe traseu, scrieţi un program care tipăreşte ordinea sosirii maşinilor la linia de sosire, respectiv informaţii despre toate depăşirile efectuate în timpul concursului.

Date de intrare

Fişierul de intrare cursa.in va conţine pe prima linie numărul de localităţi $n$. Urmează $n$ linii care descriu informaţii despre cele $n$ localităţi. Pe linia $i + 1$ din fişier se află două numere naturale $c$ şi $d$, separate prin spaţiu, cu semnificaţia că numărul de concurs al maşinii din localitatea $i$ este $c$ şi că localitatea $i$ se termină la $d$ kilometri faţă de linia de start.

Date de ieşire

Fişierul de ieşire cursa.out va conţine pe prima linie numerele de concurs ale maşinilor în ordinea sosirii lor, separate prin câte un spaţiu. În cazul în care există mai multe maşini care sosesc simultan la linia de sosire, acestea vor fi afişate în ordinea crescătoare a numerelor de concurs. Pe următoarele linii sunt descrise depăşirile, în ordinea crescătoare a localităţilor în care se produc. O depăşire este descrisă printr-o succesiune de valori de forma $L \ c \ k \ m_1 \ m_2 \ \dots \ m_k$, cu semnificaţia că în localitatea $L$ maşina cu numărul de concurs $c$ depăşeşte $k$ maşini, maşinile depăşite fiind, în ordinea în care sunt depăşite, $m_1, m_2, \dots, m_k$. Dacǎ sunt depǎşite în acelaşi moment două sau mai multe maşini, acestea se vor afişa în ordinea descrescǎtoare a numerelor de concurs.

Restricţii şi precizări

• $2 \lt n \leq 500$
• Numerele de concurs ale maşinilor sunt numere naturale nenule distincte de maxim $3$ cifre.
• Distanţa dintre linia de start şi linia de sosire (sfârşitul ultimei localităţi) $\leq 30 \ 000$
• Dacă prima cerinţă este rezolvată corect, se obţine $40\%$ din punctajul pe test. Dacă prima cerinţă este rezolvată corect, dar la afişarea depăşirilor maşinile dintr-o localitate nu sunt afişate în ordinea solicitată, se acordă $70\%$ din punctajul pe test. Punctajul integral se obţine pentru rezolvarea corectă a ambelor cerinţe.

Exemplu

cursa.in

5
10 5
66 7
99 15
35 23
70 34

cursa.out

70 35 99 10 66
3 99 2 66 10
4 35 2 66 10
5 70 4 66 10 99 35

Explicaţie

Prima localitate începe de la km $0$ şi se termină la km $5$ şi are maşina nr $10$. A doua localitate se află între km $5 - 7$ şi are maşina nr $66$. A treia localitatea se află între km $7 - 15$ şi are maşina nr $99$. A patra între km $15 - 23$ are maşina nr $35$ şi ultima între km $23 - 34$ are maşina $70$.
Ordinea de sosire a maşinilor este: $70 \ 35 \ 99 \ 10 \ 66$. Maşinile $35$ şi $99$ termină cursa deodată, se enumeră în ordinea crescătoare a numerelor.
Depăşiri:
Localitatea $3$: maşina $99$ va depăşi $2$ maşini, în ordine maşinile $66$ apoi $10$.
Localitatea $4$: maşina $35$ depăşeşte $2$ maşini, pe $66$ şi $10$ şi ajunge pe $99$ fără să o depăşească.
Localitatea $5$: maşina $70$ depăşeşte $4$ maşini, în ordine pe $66$, $10$, apoi simultan pe $99$ şi $35$ aflate la egalitate (se enumeră în ordine descrescătoare).