h2. Date de iesire

Fisierul de iesire $progresii.out$ va contine $N$ linii. Pe a $i$-a dintre aceste linii va fi scris numarul natural {$v{~i~}$}, viteza cu care alearga concurentul cu numarul {$i$} din fisierul de intrare. Daca nu exista solutie, fisierul de iesire va contine o singura linie pe care se va afla doar numarul $-1$. Daca exista mai multe solutii se va afisa cea minim lexicografica.

Fisierul de iesire $progresii.out$ va contine $N$ linii. Pe a $i$-a dintre aceste linii va fi scris numarul {$v{~i~}$}, viteza cu care alearga concurentul cu numarul {$i$} din fisierul de intrare. Daca nu exista solutie, fisierul de iesire va contine o singura linie pe care se va afla doar numarul $-1$. Daca exista mai multe solutii se va afisa cea minim lexicografica.

h2. Restrictii
* $1 ≤ N ≤ 100 000$
* $1 ≤ M, P{~i~} ≤ 2 000 000 000$
* $1 ≤ K, L ≤ 2^60^$

* Pot exista doi alergatori cu aceeasi pozitie de start
* Pozitiile de start si vitezele cu care alearga participantii la competitie sunt numere naturale
* Un sir de viteze {$(X{~1~},X{~2~}...X{~N~})$} este mai mic din punct de vedere lexicografic decat un alt sir {$(Y{~1~},Y{~2~}...Y{~N~})$} daca exista o pozitie $p$ astfel incat {$X{~p~} < Y{~p~}$} si {$X{~1~} = Y{~1~}$}, {$X{~2~} = Y{~2~}$} ... {$X{~p-1~} = Y{~p-1~}$}

* Un sir {$(a{~1~},a{~2~}...a{~N~})$} este mai mic din punct de vedere lexicografic decat un alt sir {$(b{~1~},b{~2~}...b{~N~})$} daca exista o pozitie $p$ astfel incat {$a{~p~} < b{~p~}$} si {$a{~1~} = b{~1~}$}, {$a{~2~} = b{~2~}$} ... {$a{~p-1~} = b{~p-1~}$}

h2. Exemplu
table(example). |_. progresii.in |_. progresii.out |
| 3 3 8 4
  1

  2

  2

  3
| 1
  1

h3. Explicatie

Sunt $3$ alergatori care pot bea cel mult $8$ decilitri de suc. Viteza unui alergator poate fi de maxim $3$ metri/secunda, iar pista masoara $4$ metri lungime. Primii doi concurenti vor alerga cu $1$ metru pe secunda, in timp ce ultimul va alerga cu $2$ metri/secunda. Primul concurent va bea un decilitru de suc in dreptul pozitiilor {$1$}, {$2$}, {$3$} si {$4$}, dupa care isi termina cursa. Concurentul al doilea va bea cate un decilitru in dreptul pozitiilor {$2$}, $3$ si {$4$}. Ultimul concurent va bea un singur decilitru de suc in dreptul pozitiei $3$, la momentul 0, deoarece in secunda urmatoare el va termina cursa (se va afla la distanta $5$ de capatul din stanga al pistei, care are lungimea {$4$}). In total s-au baut 8 decilitri de suc.

Primii doi concurenti vor alerga cu $1$ metru pe secunda, in timp ce ultimul va alerga cu $2$ metri/secunda. Primul concurent va bea un decilitru de suc in dreptul pozitiilor {$1$}, {$2$}, {$3$} si {$4$}, dupa care isi termina cursa. Concurentul al doilea va bea cate un decilitru in dreptul pozitiilor {$2$}, $3$ si {$4$}. Ultimul concurent va bea un singur decilitru de suc in dreptul pozitiei $3$, la momentul 0, deoarece in secunda urmatoare el va termina cursa (se va afla la distanta $5$ de capatul din stanga al pistei, care are lungimea {$4$}). In total s-au baut 8 decilitri de suc.

O alta solutie ar fi fost ({$1, 1, 3$}), dar aceasta este mai mare din punct de vedere lexicografic.
== include(page="template/taskfooter" task_id="progresii") ==

2922