popularitate

Popularitate

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

Oile sunt impartite in $M$ grupuri de prieteni, fiecare avand $N{~i~}$ membri. Fiecare oaie are asociat un numar $V{~j~}$ iar fiecare grup are asociat un numar $G{~i~}$ determinat de produsul numerelor oilor din grupul respectiv. Definim popularitate unui grup ca fiind numarul $P$ care respecta conditia $K^P^$ divide $G{~j~}$ si $K^P+1^$ nu divide $G{~j~}$, unde K este dat. In cuvinte, P reprezinta de cate ori se imparte $G{~j~}$ la $K$. Oaia Dubota este acum curioasa care este grupul cel mai popular. Ajutati-o sa gaseasca raspunsul.

Se dau $K$ si $M$ grupuri de numere. Fiecare din cele $M$ grupuri contine $N{~i~}$ numere. Fie $G{~i~}$ produsul numerelor din grupul $i$. Definim popularitatea unui grup ca fiind $P$ daca $K^P^$ divide $G{~i~}$ si $K^P+1^$ nu divide $G{~i~}$, sau, echivalent, de cate ori se imparte $G{~i~}$ la $K$. Se cere sa determinati grupul cu popularitatea maxima.

h2. Date de intrare

Fişierul de intrare $popularitate.in$ contine pe prima linie $K$. Pe a doua linia din fisier se gaseste $M$, urmeaza $M$ linii. Primul numar este $N{~i~}$, urmat de $N{~i~}$ numere reprezentand valorile asociate oilor din grupul $i$.

Fişierul de intrare $popularitate.in$ contine pe prima linie $K$, iar pe a doua linie din fisier se gaseste $M$. Pe urmatoarele $M$ linii se gasesc descrierile grupurilor. Pe linia $i+2$ prima valoare reprezinta $N{~i~}$. Ea e urmata de $N{~i~}$ numere asociate grupului $i$.

h2. Date de ieşire

În fişierul de ieşire $popularitate.out$ veti afisa 2 valori reprezentand popularitatea cea mai mare si grupul care are aceasta popularitate. In caz ca sunt mai multe grupuri care au popularitate maxima atunci afisati grupul cu indice minim.

În fişierul de ieşire $popularitate.out$ veti afisa 2 valori reprezentand popularitatea cea mai mare si grupul care are aceasta popularitate. In caz ca sunt mai multe grupuri care au popularitate maxima afisati grupul cu indice minim.

h2. Restricţii

* $1 ≤ K ≤ 100000000$

* $2 ≤ K ≤ 10000000$ ({$10$} milioane)

* $1 ≤ M ≤ 100$
* $1 ≤ N{~i~} ≤ 2000$

* $1 ≤ V{~j~} ≤ 100000000$

* Grupurile sunt formate din numere naturale din intervalul $[1, 100000000]$ ({$100$} milioane)

* Pentru $30%$ din teste $K$ este prim.
* Pentru $30%$ din teste $N{~i~} ≤ 100$.