chimichangas

Chimichangas

_Obosit fiind după filmările ultimului său film, Deadpool s-a decis să ia o mică pauză şi să deschidă un restaurant în Canada. Deadpool este de asemenea bucătarul-şef şi el poate găti un singur fel de mâncare: chimichanga. Pentru cei care nu ştiu ce este un chimichanga (să va fie ruşine!), vă puteţi gândi la un burrito prăjit._

Deadpool poate găti **$N$** tipuri unice de chimichanga, fiecare având un număr natural, cel mult egal cu **$C$**, de calorii.

Deadpool poate găti $N$ tipuri unice de chimichanga, fiecare având un număr natural, cel mult egal cu $C$, de calorii.

Restaurantul a devenit foarte cunoscut. Astăzi se află în linie **$Q$** clienţi, iar Deadpool vrea să-i impresioneze. Fiecare client comandă **$K$** feluri de mâncare şi cunoaşte exact câte calorii trebuie să consume. Mai precis, clientul **$i$** mănânca **$meal{~i~}$** calorii. Fiecare cumpărător şi-ar dori să ştie în câte moduri poate consumă numărul de calorii necesar dietei sale mâncând exact **$K$** chimichangas (nu neapărat de tipuri distincte).

Restaurantul a devenit foarte cunoscut. Astăzi se află în linie $Q$ clienţi, iar Deadpool vrea să-i impresioneze. Fiecare client comandă $K$ feluri de mâncare şi cunoaşte exact câte calorii trebuie să consume. Mai precis, clientul $i$ mănânca $meal{~i~}$ calorii. Fiecare cumpărător şi-ar dori să ştie în câte moduri poate consumă numărul de calorii necesar dietei sale mâncând exact $K$ chimichangas (nu neapărat de tipuri distincte).

!>problema/chimichangas?deadpool.png!
h2. Date de intrare

Fişierul de intrare $chimichangas.in$ va conţine pe prima linie **$2$** numere naturale, **$N$** şi **$K$**. Pe următoarea linie se află **$N$** valori distincte, **$calorie{~i~}$** reprezentând numărul de calorii din al **$i$**-ulea tip de _chimichanga_. Pe cea de a treia linie se află numărul de întrebări **$Q$**. Apoi, pentru fiecare client $1 ≤ i ≤ Q$ se află pe linia $i + 3$ numărul de calorii necesare dietei sale, **$meal{~i~}$**.

Fişierul de intrare $chimichangas.in$ va conţine pe prima linie $2$ numere naturale, $N$ şi $K$. Pe următoarea linie se află $N$ valori distincte, $calorie{~i~}$ reprezentând numărul de calorii din al $i$-ulea tip de _chimichanga_. Pe cea de a treia linie se află numărul de întrebări $Q$. Apoi, pentru fiecare client $1 ≤ i ≤ Q$ se află pe linia $i + 3$ numărul de calorii necesare dietei sale, $meal{~i~}$.

h2. Date de ieşire

În fişierul de ieşire $chimichangas.out$ va conţine **$Q$** linii. Fiecare linie va conţine un singur număr, răspunsul întrebării aferente. Pentru că acest număr poate să fie mare, vi se cere să îl afişaţi restul împărţirii acestuia la **$2999$**.

În fişierul de ieşire $chimichangas.out$ va conţine $Q$ linii. Fiecare linie va conţine un singur număr, răspunsul întrebării aferente. Pentru că acest număr poate să fie mare, vi se cere să îl afişaţi restul împărţirii acestuia la $2999$.

h2. Restricţii

* $1 ≤ C ≤ N$
* $0 ≤ W ≤ 1.000.000.000$
* $1 ≤ Q ≤ 200.000$

* Deadpoll are la dispoziţie o **cantitate nelimitată** pentru fiecare tip de chimichanga.

* Deadpool are la dispoziţie o **cantitate nelimitată** pentru fiecare tip de chimichanga.

* Ordinea în care fiecare client mănâncă este relevantă, spre exemplu $(1 + 2)$ este diferit de $(2 + 1)$.
* **Nu** vor exista două tipuri de chimichanga cu acelaşi număr de calorii.

* Valorile trebuie afişate **modulo 2999**.

* Valorile trebuie afişate **modulo $2999$**.

* Testele vor fi grupate aşa cum reiese din tabelul de mai jos.
table(example). |_. Grup |_. Punctaj |_. Restricţii adiţionale |

|1 | 20 | $**N** ≤ 100$, $**K** ≤ 10$, $**W** ≤ 2.000$ şi $**C** ≤ 500$|
|2 | 5 | $**K** = 2$, $**W** ≤ 60.000$ şi $**Q** ≤ 100$|
|3 | 25 | $**C x K** ≤ 10.000$ şi $**W** ≤ 50.000$|
|4 | 20 | $**C x K** ≤ 30.000$ |

|1 | 20 | $N ≤ 100$, $K ≤ 10$, $W ≤ 2 000$ şi $C ≤ 500$|
|2 | 5 | $K = 2$, $W ≤ 60 000$ şi $Q ≤ 100$|
|3 | 25 | $C * K ≤ 10 000$ şi $W ≤ 50 000$|
|4 | 20 | $C * K ≤ 30 000$ |

|5 | 30 | niciuna|
h2. Exemplu

Sunt $5$ moduri de a mânca $8$ calorii: $(1 + 1 + 1 + 5), (1 + 1 + 5 + 1), (1 + 5 + 1 + 1), (5 + 1 + 1 + 1), (2 + 2 + 2 + 2)$.
|

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

==Include(page="template/taskfooter" task_id="chimichangas") ==