DENIS

#include<iostream>
#include<cmath>
#include<fstream>
using namespace std;
ifstream fin("exp.in");
ofstream fout("exp.out");
double x[30004];
int ap[30004];
int main()
{
    int n,m,i,d,aux,r,p,apd,ok=1;;
    fin>>m>>n;
    fout<<"1\n";
    for(i=1; i<=n; i++)
    {
        fin>>x[i];
        aux=x[i];
        r=sqrt(aux);
        d=2;
        while(aux>1)
        {
            p=0;
            while(aux%d==0)
            {
                p++;
                aux/=d;
            }
            ap[d]+=p;
            if(d*d<aux)
            {
                d++;
            }
            else
            {
                d=aux;
            }
        }
    }
    for(i=1; i<=30000; i++)
    {
        if(ap[i]%m==0 && ap[i])
        {
            fout<<i<<" "<<ap[i]/m<<'\n';
        }
        else
        {
            if(ap[i]%m)
            {
                fout.close();
                fout.open("exp.out",ios::out);
                fout<<"0";
                fout.close();
                fin.close();
                return 0;
            }
        }
    }
    fout.close();
    fin.close();
    return 0;
}