Fişierul intrare/ieşire:	progresii.in, progresii.out	Sursă	preONI 2008, Runda finala
Autor	Adrian Airinei, Filip Cristian Buruiana	Adăugată de	Airinei Adrian •astronomy
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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₁ + T₂ + ... 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).

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.

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.

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.

Restrictii

• 1 ≤ N ≤ 100 000
• 1 ≤ P_i ≤ 2 000 000 000
• 1 ≤ M ≤ 2 000 000 000
• 1 ≤ K, X ≤ 2⁶⁰
• 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

Exemplu

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.

Cum se trimit solutii?