#include <fstream>
using namespace std;
ifstream fin("arma1.in");
ofstream fout("arma1.out");
int xlan(int x, int n)
{
    int p=1;
    while(n>0)
    {
        p=p*x;
        n--;
    }
    return p;
}
int prim(int n)
{
    if(n<2) return 0;
    if(n%2==0 && n!=2) return 0;
    for(int d=3;d*d<=n;d=d+2)
        if(n%d==0) return 0;
    return 1;
}
int cmmdc(int a, int b)
{
    while(b>0)
    {
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int A[10001],D[10001],E[10001],l;
bool Er[50001];
int P[50001],np;
int main()
{
    int max=50000;
    for(int i=2;i<=max;i++)
        Er[i]=1;
    for(int i=2;i*i<=max;i++)
        if(Er[i]==1)
            for(int j=i*i;j<=max;j=j+i)
                Er[j]=0;
    for(int i=2;i<=max;i++)
        if(Er[i]==1) P[++np]=i;
    /*for(int i=1;i<=np;i++) fout<<P[i]<<" ";*/
    int p,n;
    fin>>p>>n;
    for(int i=1;i<=n;i++)
        fin>>A[i];
    if(p==1)
    {
        long long s=0;
        for(int i=1;i<=n;i++)
        {
            l=0;
            int x=A[i];
            if(prim(x) || x==0) s=s+x;
            else
            {
                int d=1; //descompunere numar
                while(x>1)
                {
                    if(x%P[d]==0)
                    {
                        int e=0;
                        while(x%P[d]==0)
                        {
                            e++;
                            x=x/P[d];
                        }
                        l++;
                        E[l]=e; //retin exponetul
                        D[l]=P[d]; //retin baza
                    }
                    else d++;
                    if(P[d]*P[d]>x && x!=1)
                    {
                        l++;
                        D[l]=x;
                        E[l]=1;
                        x=1;
                    }
                }
                int cmmdc1=0,w=E[1]; //calculez cmmdc-ul exponentilor
                for(int q=1;q<=l;q++)
                    if(E[q]==1)
                    {
                        cmmdc1=1;
                        break;
                    }
                    else
                    {
                        int y=E[q];
                        cmmdc1=cmmdc(y,w);
                        w=cmmdc1;
                    }
                if(cmmdc1==1) s=s+A[i];
                else
                {
                    int r=1;
                    for(int q=1;q<=l;q++)
                        {
                            E[q]=E[q]/cmmdc1;
                            r=r*xlan(D[q],E[q]);
                        }
                    s=s+r;
                }
            }
        }
        fout<<s;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            l=0;
            int x=A[i];
            if(prim(x) || x==1) fout<<1<<"\n";
            else
            {
                int d=1; //descompunere numar
                while(x>1)
                {
                    if(x%P[d]==0)
                    {
                        int e=0;
                        while(x%P[d]==0)
                        {
                            e++;
                            x=x/P[d];
                        }
                        l++;
                        E[l]=e; //retin exponetul
                        D[l]=P[d]; //retin baza
                    }
                    else d++;
                    if(P[d]*P[d]>x && x!=1)
                    {
                        l++;
                        D[l]=x;
                        E[l]=1;
                        x=1;
                    }
                }
                int cmmdc1=0,w=E[1]; //calculez cmmdc-ul exponentilor
                for(int q=1;q<=l;q++)
                    if(E[q]==1)
                    {
                        cmmdc1=1;
                        break;
                    }
                    else
                    {
                        int y=E[q];
                        cmmdc1=cmmdc(y,w);
                        w=cmmdc1;
                    }
                fout<<cmmdc1<<"\n";
            }
        }
    }
    return 0;
}