== 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:

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

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

h2. Cerinta

Dintre toate sirurile Q ce indeplinesc proprietatile de mai sus trebuie determinat cel minim lexicografic.

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

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

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

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 8 4

| 3 3 7 4

  1
  2
  3

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.

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.

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