Se dă un şir de n numere naturale nenule x1, x2, …, xn şi un număr natural m.

Cerința

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

Date de intrare

Fișierul de intrare exp.in conține pe prima linie m, pe linia a doua n, iar pe linia a treia numerele x1, x2, …, xn separate între ele prin câte un spațiu.

Date de ieșire

În fișierul de ieșire exp.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>=1). Aceste perechi se vor scrie în ordine crescătoare după primul număr (adică p).

Restricții și precizări

• 0 < n < 5000
• 0 < xi < 30.001, pentru orice i=1..n
• m poate fi una din cifrele 2, 3, 4.

Exemplul 1:

exp.in

2
4
32 81 100 19

exp.out

0

Exemplul 2:

exp.in

2
4
32 81 100 18

exp.out

1
2 4
3 3
5 1