expresie

Se dă un șir de $n$ numere naturale nenule $x_1, x_2, \dots, x_n$ și un număr natural $m$.

Cerință

Să se verifice dacă valoarea expresiei $\sqrt[m]{x_1 x_2 x_3 \dots x_n}$ este un număr natural. În caz afirmativ să se afișeze acest număr descompus în factori primi.

Date de intrare

În fișierul expresie.in se află pe prima linie $m$, pe linia a doua $n$, iar pe linia a treia numerele $x_1$, $x_2$, $\dots$, $x_n$ separate între ele prin câte un spațiu.

Date de ieșire

În fișierul expresie.out se va scrie pe prima linie cifra $0$, dacă valoarea expresiei nu este un număr natural, respectiv $1$ dacă este un număr natural.
Dacă valoarea expresiei este un număr natural, pe următoarele linii se vor scrie perechi de forma "$p\ e$" ($p$ este factor prim care apare în descompunere la puterea $e \geq 1$). Aceste perechi se vor scrie în ordine crescătoare după primul număr (adică $p$).

Restricții

• $n$ este un număr natural nenul mai mic strict decât $5\ 000$.
• $x_i$ este un număr natural nenul mai mic strict decât $30\ 000$, $i \in \{1, 2, \dots, n\}$.
• $m$ poate fi una din cifrele $2$, $3$ sau $4$.

Exemplul 1

expresie.in

2
4
32 81 100 19

expresie.out

0

Explicație

$\sqrt[2]{32 \cdot 81 \cdot 100 \cdot 19}$ nu este număr natural.

Exemplul 2

expresie.in

2
4
32 81 100 18

expresie.out

1
2 4
3 3
5 1

Explicație

$\sqrt[2]{32 \cdot 81 \cdot 100 \cdot 18} = 2^4 \cdot 3^3 \cdot 5^1$