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

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:

h2. Cerinta

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

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.

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

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

h2. Restrictii
* $1 ≤ N ≤ 100 000$
* $1 ≤ M, P{~i~} ≤ 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{~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 7 4

| 3 3 8 4

  1
  2
  3

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.

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.

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