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

Intr-o zi cand se plictiseau, Ana si prietenele ei au inceput sa se joace. Fetele au o floare cu $N$ petale si la o mutare au voie sa rupa maxim $K$ dintre ele. Traditia spune ca norocoasa care ia ultimele petale ale florii va primi $M$ trandafiri rosii, cea care ar fi trebuit sa mute urmatoarea va primi $M - 1$ trandafiri rosii si asa mai departe pana la cea care a mutat exact inainte de castigatoare, care primeste $1$ trandafir. Ana poate stabili ordinea in care fetele vor intra in joc. Ajutati-o sa castige cei $M$ trandafiri.

h2. Date de intrare

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.

Fişierul de intrare $floare.in$ contine cele $3$ numere, $M$ - numarul de jucatoare, $N$ - numarul de petale si $K$ - numarul maxim de petale care pot fi luate la o mutare

h2. Date de ieşire

În fişierul de ieşire $floare.out$ se vor afla $T$ numere, pozitia fetei castigatoare pentru fiecare dintre cele $T$ runde de joc.

În fişierul de ieşire $floare.out$ se va afla un singur numar, pozitia fetei care va castiga jocul.

h2. Restricţii si precizari

* $1 ≤ T ≤ 100$
* $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 valorile pentru $N$ vor fi mai mici sau egale cu $1 000$

* $1 ≤ M ≤ 200000$
* $1 ≤ N ≤ 200000$
* $1 ≤ K ≤ N$
* Se stie ca fiecare fata vrea sa maximizeze numarul de trandafiri pe care ii va primi la sfarsit
* Pentru teste in valoare de cel putin $40$ de puncte $N ≤ 1000$

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

|2 3 1
2 1
6

|2 6 3

| 1
|
h3. Explicaţie

O strategie castigatoare pentru prima jucatoare in exemplul de mai sus ar putea fi: ia $2$ petale, floarea ramane cu $4$ petale. De aici oricate petale ar rupe a $2$-a jucatoare ( $1$, $2$ sau $3$), prima jucatoare va putea sa ia tot ce a ramas.

O strategie castigatoare pentru prima jucatoare in exemplul de mai sus ar putea fi: ia $2$ petale, a $2$-a jucatoare ramane cu $4$. De aici oricate petale ar rupe ($1$, $2$ sau $3$) prima jucatoare va putea sa ia tot ce a ramas.

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

4267