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

Gigel are $N$ tricouri, fiecare tricou avand inscriptionat ca model un numar cunoscut de buline. Ionel, uitandu-se un pic la tricouri, il roaga pe Gigel sa selecteze un numar de $K$ tricouri din cele $N$ care sa aibe in total un numar de buline divizibil cu $P$. Gigel, pretentios din fire, ii alege acele tricouri care au inscriptionate in total un numar maxim de buline si au si proprietatea ceruta.

Gigel are $N$ tricouri, fiecare tricou avand inscriptionat ca model un numar cunoscut de buline cuprins intre $1$ si $1 000 000$. Ionel, uitandu-se un pic la tricouri, il roaga pe Gigel sa selecteze un numar de $K$ tricouri din cele $N$ care sa aibe in total un numar de buline divizibil cu $P$. Gigel, pretentios din fire, ii alege acele tricouri care au inscriptionate in total un numar maxim de buline si au si proprietatea ceruta.

Pentru $M$ cerinte ale lui Ionel de forma precizata mai sus, sa se determine care este numarul maxim de buline divizibil la $P$, in urma alegerii a exact $K$ tricouri.
h2. Date de intrare

h2. Restrictii
* {$3 ≤ N ≤ 300 000$}

* {$3 ≤ M ≤ 100$}

* Pentru fiecare cerinta a lui Ionel, {$1 ≤ K ≤ 20$} si {$2 ≤ P ≤ 20$}

* Numarul de buline de pe fiecare tricou este un numar natural cuprins intre $1$ si $1 000 000$

h2. Exemplu