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

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

h2. Cerinta

h2. Date de intrare

Fisierul de intrare $progresii.in$ ...

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

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

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 ≤ P{~i~} ≤ 2 000 000 000$
* $1 ≤ M ≤ 2 000 000 000$
* $1 ≤ K, X ≤ 2^60^$
* 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~}$

h2. Exemplu