== 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+3*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 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$).

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

h2. Date de intrare

Fisierul de intrare $progresii.in$ contine pe prima linie, separate printr-un spatiu, numerele $N$, $M$, $K$ si $X$, avand semnificatia din enunt. Pe urmatoarele $N$ linii se afla informatii despre progresii, pe linia $i+1$ aflandu-se $P{~i~}$, primul termen al progresiei $i$.

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$ se vor afisa $N$ linii, pe linia $i$ aflandu-se $Q{~i~}$, ratia progresiei $i$. Daca nu exista solutia se va afisa doar $-1$.

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 ≤ P{~i~} ≤ 2 000 000 000$
* $1 ≤ M ≤ 2 000 000 000$
* $1 ≤ K, X ≤ 2^60^$
* Toate numerele din fisierul de intrare sunt naturale, de asemenea sirul $Q$ trebuie sa contina numai numere naturale
* Un sir $A$ este mai mic din punct de vedere lexicografic decat un sir $B$ daca exista o pozitie $k$ astfel incat $A{~i~}=B{~i~}$ pentru $i<k$ si $A{~k~}<B{~k~}$

* $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 |

| 3 3 7 4

| 3 3 8 4

  1

  2

  2

  3
| 1
  1

h3. Explicatie

Prima progresie contine 4 termeni mai mici sau egali decat 4 (1, 2, 3, 4). A doua contine 3 termeni (2, 3, 4) iar cea de-a treia niciun termen mai mic sau egal decat 4. In total sunt 7 termeni. O solutie posibila pentru sirul $Q$ era si $Q = {1, 1, 3}$, dar aceasta este mai mare din punct de vedere lexicografic.

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