== include(page="template/taskheader" task_id="floare") ==

Intr-o zi cand se plictiseau, Ana si prietenele ei au inventat un nou joc, pe care l-au jucat de $T$ ori. Fetele au o floare cu $N$ petale si la o mutare au voie sa rupa minim una si maxim $K$ dintre ele. Traditia spune ca norocoasa care ia ultimele petale ale florii va primi $A$~0~ trandafiri rosii, cea care ar fi trebuit sa mute urmatoarea va primi $A$~1~ trandafiri rosii si asa mai departe pana la cea care a mutat exact inainte de castigatoare, care primeste $A$~N-1~ trandafiri. Ana poate stabili ordinea in care fetele vor rupe petalele. Ajutati-o, pentru fiecare dintre cele $T$ jocuri, sa castige cat mai multi trandafiri.

Intr-o zi cand se plictiseau, Ana si prietenele ei au inventat un nou joc, pe care l-au jucat de $T$ ori. Fetele au o floare cu $N$ petale si la o mutare au voie sa rupa minim una si maxim $K$ dintre ele. Traditia spune ca norocoasa care ia ultimele petale ale florii va primi $A$~0~ trandafiri rosii, cea care ar fi trebuit sa mute urmatoarea va primi $A$~1~ trandafiri rosii si asa mai departe pana la cea care a mutat exact inainte de castigatoare, care primeste $A$~M-1~ trandafiri. Ana poate stabili ordinea in care fetele vor rupe petalele. Ajutati-o, pentru fiecare dintre cele $T$ jocuri, sa castige cat mai multi trandafiri.

h2. Date de intrare

Fişierul de intrare $floare.in$ contine pe prima linie cele $3$ numere, $M$ - numarul de jucatoare, $T$ - numarul de jocuri si $K$ - numarul maxim de petale care pot fi luate la o mutare. Pe cea de-a doua linie se gaseste sirul $A$. Pe fiecare dintre urmatoarele $T$ linii se gaseste $N$ - numarul de petale ale florii pentru jocul respectiv.

Fişierul de intrare $floare.in$ contine pe prima linie cele $3$ numere, $M$ - numarul de jucatoare, $K$ - numarul maxim de petale care pot fi luate la o mutare si $T$ - numarul de jocuri. Pe cea de-a doua linie se gaseste sirul $A$. Pe fiecare dintre urmatoarele $T$ linii se gaseste $N$ - numarul de petale ale florii pentru jocul respectiv.

h2. Date de ieşire

h2. Restricţii si precizari
* $1 ≤ T ≤ 100$

* $1 ≤ M ≤ 200000$
* $1 ≤ N ≤ 200000$
* $1 ≤ K ≤ N$

* $1 ≤ M ≤ 200 000$
* $1 ≤ N ≤ 200 000$
* $1 ≤ K ≤ 200 000$

* Se stie ca fiecare fata joaca optim, adica vrea sa castige cat mai multi trandafiri
* Valorile din sirul $A$ sunt distincte

* Pentru teste in valoare de cel putin $30$ de puncte $N ≤ 1000$

* Pentru teste in valoare de cel putin $30$ de puncte valorile pentru $N$ vor fi mai mici sau egale cu $1 000$

h2. Exemplu
table(example). |_. floare.in |_. floare.out |

|2 6 3

|2 3 1

2 1

6

| 1
|

4267