lampion

LLM are o muțime de prieteni în toată lumea, mai exact $N$. De ziua lui, decide ca împreună cu prietenii săi, să lanseze lampioane. Fiecare lampion are asociată o valoare $a_i$. Lansarea lampioanelor se face după următoarea regulă:

În primul minut, LLM și prietenii lui vor marca lampioanele cu valoarea divizibilă cu 2, în următorul minut vor marca lampioanele cu valoarea divizibilă cu 3, în următorul minut, cele cu valoarea divizibilă cu 5 ... La al $i$-lea minut vor marca lampioanele cu valoarea divizibilă cu $p_i$, unde $p_i$ este al $i$-lea număr prim.

De asemenea, în fiecare minut vor lansa acele lampioane a căror valoare $a_i$ are toți divizorii primi marcați.

Cerință

Se dă $P$, $N$ și șirul $a_1$, $a_2$, ..., $a_N$.

Dacă $P = 1$, să se afișeze câte lampioane care au valorile asociate numere prime au fost lansate în primul minut.

Dacă $P = 2$, să se afișeze, în ordine crescătoare, valorile libere de pătrate asociate lampioanelor lansate în primele două minute.

Dacă $P = 3$, să se afișeze numărul minim de minute după care vor fi lansate cel puțin $K$ lampioane.

Date de intrare

Pe prima linie a fișierului de intrare lampion.in se află numerele naturale $P$, $N$ și $K$. Pe cea de-a 2-a linie se află $N$ numere naturale separate prin câte un spațiu, reprezentând șirul $a$.

Date de ieșire

Pe prima linie din fișierul de ieșire lampion.out, se află răspunsul la cerința $P$. Dacă $P = 1$, pe prima linie a fișierului de ieșire, se va afla numărul de lampioane care au valorile asociate numere prime și au fost lansate în primul minut. Dacă $P = 2$, se vor afișa, pe prima linie a fișierului de ieșire, valorile libere de pătrate asociate lampioanelor lansate în primele două minute, în ordine crescătoare, separate prin câte un spațiu. Dacă $P = 3$, se afișează pe prima linie a fișierului de ieșire, un singur număr natural reprezentând numărul minim de minute după care vor fi lansate cel puțin $K$ lampioane.

Restricții și precizări

• Un număr este liber de pătrate dacă nu este divizibil cu alt pătrat perfect în afară de 1.
• $1 \leq K \leq N \leq 1 \ 000 \ 000$
• $2 \leq a_i \leq 5 \ 000 \ 000$, pentru oricare $1 \leq i \leq N$
• Pentru 20 de puncte $P = 1$.
• Pentru 30 de puncte $P = 2$.
• Se garantează că dacă $P = 2$, va exista cel puțin un lampion care este lansat în primele două minute.

Exemplul 1

lampion.in

1 7 7
10 6 11 5 2 38 33

lampion.out

1

Exemplul 2

lampion.in

2 7 7
10 6 11 5 2 38 33

lampion.out

2 6

Exemplul 3

lampion.in

3 7 7
10 6 11 5 2 38 33

lampion.out

8

Explicații

În primul exemplu:

Singurul lampion care este lansat în primul minut este cel care are valoarea 2 asociată.

În al doilea exemplu:

În primul minut este lansat lampionul cu valoarea 2, iar în al doilea minut este lansat lampionul cu valoarea 6, deci după primele două minute sunt lansate lampioanele cu valorile 2 și 6.

În al treilea și al patrulea exemplu:

În primul minut este lansat lampionul cu valoarea 2.

În al doilea minut este lansat lampionul cu valoarea 6.

În al treilea minut sunt lansate lampioanele cu valorile 5 și 10.

În al patrulea minut nu este lansat niciun lampion.

În al cincilea minut sunt lansate lampioanele cu valorile 11 și 33.

În al șaselea și al șaptelea minut nu este lansat niciun lampion.

În al optulea minut este lansat lampionul cu valoarea 38.

Deci, numărul minim de minute după care sunt lansate cel puțin 4 lampioane este 3, iar numărul minim de minute după care sunt lansate cel puțin 7 lampioane este 8.