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

O progresie aritmetica este un sir infinit de numere naturale nenule astfel incat diferenta dintre oricare doi termeni consecutivi din sir este constanta. Astfel, o progresie aritmetica este definita in mod unic de primul termen al sirului si de diferenta dintre doi termeni consecutivi (ratia).
Se dau numerele naturale $X$, $K$ si {$M$}, precum si $N$ progresii pentru care primul termen este cunoscut iar ratia trebuie determinata. Trebuie sa aflam un sir de ratii $Q$ = {{$Q{~1~}$}, {$Q{~2~}$}, ..., {$Q{~N~}$}}, unde {$Q{~i~}$} este ratia pentu progresia ce are primul termen {$P{~i~}$}, care sa indeplineasca simultan proprietatile:

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.

* {$1 ≤ Q{~i~} ≤ M$}, {$Q{~i~}$} natural, pentru orice $i$ de la $1$ la $N$
* Numarul de numere mai mici sau egale cu $X$ din toate progresiile este maxim $K$
 
Dintre toate sirurile Q ce indeplinesc proprietatile de mai sus trebuie determinat cel minim lexicografic.

h2. Date de intrare

Fisierul de intrare $progresii.in$ contine pe prima linie, separate printr-un spatiu, numerele naturale $N$, $M$, $K$ si $X$, avand semnificatia din enunt. Fiecare din urmatoarele $N$ linii contine cate un numar natural. Astfel, pe linia $i+1$ se va afla {$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

Fisierul de iesire $progresii.out$ va contine $N$ linii. Pe a $i$-a dintre aceste linii va fi scris numarul {$Q{~i~}$}, ratia progresiei ce are primul termen egal cu $P{~i~}$. Daca nu exista solutie, fisierul de iesire va contine o singura linie pe care se va afla doar numarul $-1$.

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, X ≤ 2^60^$

* $1 ≤ K, L ≤ 2^60^$

* 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

h3. Explicatie

Cele $3$ progresii vor fi: ({$1,2,3,4,5,6...$}), ({$2,3,4,5,6...$}) si ({$3,5,7,9...$}). Prima progresie contine $4$ termeni mai mici sau egali decat $4$, a doua contine $3$ termeni, iar ultima progresie contine un singur termen. In total sunt $8$ termeni mai mici sau egali decat {$4$}. O solutie posibila pentru sirul $Q$ era si $Q = {1, 1, 3}$, dar aceasta este mai mare din punct de vedere lexicografic.

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") ==