== include(page="template/taskheader" task_id="progresii") ==

O progresie aritmetica cu ratia $Q$ si primul termen $P$ este un sir infinit de termeni de forma: $P$, $P+Q$, $P+2*Q$ ... $P+k*Q$ (forma generala a unui termen din progresie este $P+k*Q$, $k$ numar natural). Irina a primit de la Ana $N$ progresii aritmetice, dar a uitat care este ratia fiecarei progresii. Astfel, pentru fiecare progesie $i$ ea stie primul termen al progresiei $P{~i~}$. Irina trebuie sa fixeze acum pentru fiecare progresie $i$ o ratie $Q{~i~}$. Ana insa ii complica putin misiunea, si calculeaza pentru fiecare progresie $i$ o valoare $T{~i~}$, care semnifica cati termeni din progresia $i$ sunt mai mici sau egali decat $X$. Apoi calculeaza $SUM = T{~1~} + T{~2~} + ... T{~N~}$ si doreste ca aceasta valoare $SUM$ sa fie mai mica sau egala decat $K$. O ultima conditie a Anei este ca $1≤Q{~i~}≤M$ (pentru fiecare $i$ de la $1$ la $N$).
Determinati pentru Irina sirul $Q$ de ratii care sa satisfaca toate conditiile impuse de Ana. Daca exista mai multe solutii, se va afisa cea mai mica solutie din punct de vedere lexicografic.

La o competitie sportivo-matematica denumita sugestiv "Progresii pentru toti" participa $N$ concurenti. Pista pe care alearga acestia este dreapta si are lungimea de $L$ metri. Pentru fiecare concurent $i$ se cunoaste pozitia {$P{~i~}$} de la care isi incepe alergarea, relativ cu capatul de start al pistei. Fiecare alergator poate alerga cu o viteza constanta intre $1$ metru/secunda si $M$ metri/secunda. Astfel, daca alergatorul $i$ alearga cu {$v{~i~}$} metri/secunda, la secunda $j$ el se va afla la pozitia {$P{~i~} + v{~i~} * j$}. Deoarece caldura din ziua competitiei este inabusitoare, fiecare concurent bea un decilitru de suc energizant la fiecare secunda alergata pe pista.
Pentru ca este o competitie in scopuri caritabile, organizatorii doresc sa stranga un profit cat mai mare. De aceea ei doresc sa stabileasca pentru fiecare alergator viteza cu care trebuie sa alerge astfel incat cantitatea de suc energizant care este bauta in total de cei $N$ alergatori sa nu depaseasca valoarea de $K$ decilitri. Daca exista mai multe solutii se va afisa cea minim lexicografica.
 

h2. Date de intrare

Fisierul de intrare $progresii.in$ ...

Fisierul de intrare $progresii.in$ contine pe prima linie, separate printr-un spatiu, numerele naturale $N$, $M$, $K$ si $L$, avand semnificatia din enunt. Fiecare din urmatoarele $N$ linii contine cate un numar natural. Astfel, pe linia $i+1$ se va afla {$P{~i~}$}, pozitia de start a alergatorului cu numarul {$i$}.

h2. Date de iesire

In fisierul de iesire $progresii.out$ ...

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.

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~}$}

h2. Exemplu
table(example). |_. progresii.in |_. progresii.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3 8 4
  1
  2
  3
| 1
  1
  2

|
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.
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