norocos

Un număr natural nenul $m$ se numește norocos dacă pătratul lui se poate scrie ca sumă de $m$ numere naturale consecutive. Un număr natural $m$ se numește $k$-norocos, dacă este egal cu produsul a exact $k$ numere prime distincte. Observați că între cele două proprietăți definite nu există nicio legătură.

Cerinţă

Dându-se $k$ și $N$ numere naturale, scrieți un program care să determine:

1. Cel mai mic și cel mai mare număr norocos dintre cele $N$ numere citite;
2. Câte numere $k$-norocoase sunt în șirul de $N$ numere citite.

Date de intrare

Fişierul de intrare norocos.in conţine pe prima linie un număr natural $C$. Pentru toate testele de intrare, numărul $C$ are una din valorile $1$ sau $2$. Pe linia a doua a fișierului se găsesc numerele naturale $N$ și $k$, cu semnificația din enunț, iar pe a treia linie se găsesc $N$ numere naturale, separate prin câte un spațiu.

Date de ieşire

Fișierul de ieșire este norocos.out.
Dacă $C = 1$, se va rezolva numai cerința 1). În acest caz, în fişierul de ieşire se vor scrie, separate printr-un spațiu, în această ordine, cel mai mic și cel mai mare număr norocos dintre cele $N$ numere citite. Dacă nu există niciun număr norocos se va afișa valoarea $0$. Dacă există un singur număr norocos, acesta se va afișa de două ori.

Dacă $C = 2$, se va rezolva numai cerința 2) În acest caz, în fişierul de ieşire se va scrie un singur număr reprezentând numărul de numere $k$-norocoase citite.

Restricţii și precizări

• $1 ≤ N ≤ 1 \ 000$
• $2 ≤ k ≤ 30$
• Numerele citite de pe a treia linie a fișierului sunt numere naturale între $1$ și $2 \ 000 \ 000 \ 000$.
• Pentru rezolvarea corectă a primei cerinţe se acordă 40 de puncte.
• Pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60 de puncte.

Exemplul 1

norocos.in

1
9 3
165 12 33 30 5 18 105 15 4

norocos.out

5 165

Explicație

Atenție, $C = 1$, deci se va rezolva doar prima cerință.
Cel mai mic număr norocos este $5$
$5^2 = 25 = 3+4+5+6+7$

Cel mai mare număr norocos este $165$
$165^2 = 27225 = 83+84+85+...+246+247$

Observați faptul că, deși se citește valoarea lui $k$, aceasta nu este folosită în rezolvarea cerinței $1$.

Exemplul 2

norocos.in

2
5 3
165 31 165 105 44

norocos.out

3

Explicație

Atenție, $C = 2$, deci se va rezolva doar a doua cerință.
Cele trei numere $k$-norocoase sunt $165$, $165$, $105$