Pătrățel deține un teren agricol format din $n$ parcele. El a achiziționat mașini de semănat de ultimă generație, care funcționează într-un mod particular. Fiecare mașină are o capacitate de semănat $P$ și este fixată pe una dintre parcele. Numărul de semințe plantate de mașină pe o parcelă se determină folosind formula $P - d$, unde $d$ reprezintă distanța în parcele față de mașina de semănat. În locația exactă a mașinii, unde distanța $d$ este $0$, se plantează exact $P$ semințe. Pe parcelele adiacente, numărul de semințe scade pe măsură ce distanța față de mașină crește, iar procesul de semănat se oprește când $P - d$ ajunge la $0$.

Terenul lui Pătrățel include parcele cu ziduri, pe care nu se pot planta semințe. Zidurile blochează răspândirea semințelor dincolo de parcela respectivă. Mașinile opresc procesul de semănare, de asemenea, la capetele terenului, la stânga și la dreapta. Două mașini pot semăna semințe pe aceeași parcelă, întrucât nu interferează între ele.

Cerință

Sarcina voastră este să corectați un program scris deja de altcineva care afișează cum arată fiecare parcelă după semănat. Îl puteți găsi aici sau în secțiunea „Atașamente” din lateral.
În parcelele cu ziduri, trebuie să afișați $-1$. Pentru celelalte parcele, indicați numărul total de semințe plantate, luând în considerare amplasarea mașinilor de semănat și prezența zidurilor.

Date de intrare

Pe prima linie se citește $L$, reprezentând lungimea terenului exprimată în numărul de parcele.
Pe a doua linie se citește $Z$, numărul de parcele cu ziduri.
Pe a treia linie se citesc $Z$ numere care reprezintă indicii zonelor cu ziduri. Indicii sunt numerotați începând de la $1$ (vezi exemplul).

Pe linia următoare, se citește $M$, numărul de mașini de semănat.
Pe următoarele $M$ linii se citesc perechi de valori $P \ T$, reprezentând:

• $P$ — puterea de semănat a mașinii.
• $T$ — poziția mașinii pe teren. Indexarea se face începând de la $1$.

Date de ieșire

La finalul procesului de semănat, afișați starea fiecărei parcele de teren. Pentru fiecare parcelă, afișați numărul total de semințe plantate în acea zonă. În cazul parcelelor care conțin ziduri, afișați valoarea $-1$.

Rezultatele vor fi afișate pe o singură linie, separate prin spațiu. Fiecare număr afișat reprezintă fie numărul de semințe de pe o parcelă, fie valoarea $-1$ pentru parcelele cu ziduri.

Restricții și precizări

• $1 \le L \le 10\ 000$
• $0 \le Z \le L$
• $1 \le M \le 1\ 000$
• Pentru fiecare mașină, $1 \le P \le 500$.

Exemplul 1

stdin

21
4
1 4 8 21
3
20 2
5 6
3 15

stdout

-1 20 19 -1 4 5 4 -1 0 0 0 0 1 2 3 2 1 0 0 0 -1

Explicație

• Mașina $1$ (putere: $20$, locație: $2$) nu poate semăna la stânga din cauza zidului, dar seamănă $19$ semințe la dreapta, până la următorul zid.
• Mașina $2$ (putere: $5$, locație: $6$) seamănă spre stânga și dreapta, dar este blocată de ziduri pe ambele direcții.
• Mașina $3$ (putere: $3$, locație: $15$) seamănă câteva semințe în ambele direcții, când puterea sa se epuizează, aceasta se oprește. Nu atinge niciun zid până la oprire!

Exemplul 2

stdin

5
2
3 5
2
15 2
15 4

stdout

14 15 -1 15 -1

Explicație

• Mașina $1$ (putere: $15$, locație: $2$) poate semăna pe parcela sa, și în stânga, până la marginea terenului, iar zidul de pe parcela $3$ o blochează în dreapta.
• Mașina $2$ (putere: $15$, locație: $4$) seamănă doar pe parcela sa, deoarece este blocată de ziduri în ambele părți.