#include<bits/stdc++.h>
using namespace std;

long long N,D[100'005];
int F; // factor

// nule su to zbog indeksiranja od keca

int manjifaktor[100005];
int kolicnik[100005];

long long sol[100005]={0, 1, };

long long izlaz[100005];
unordered_map<long long,int> inverz1,inverz2; // OK

long long Euklid(long long a,long long b){
    int c;
    while(b){
        c=a%b;
        b=c;
        a=b;
    }
    return a;
}

int main(){
    scanf("%d%d",&N,&F);
    for(int i=1;i<=F;++i){
        scanf("%d",&D[i]);
        inverz1[D[i]]=i;
    }

    sort(D+1,D+1+F);

    for(int i=1;i<=F;++i)
        inverz2[D[i]]=i;

    for(int i=2;i<=F;++i){
        for(int j=2;j<i;++j)
            if(D[i]%D[j]==0) manjifaktor[i]=j;
        if(!manjifaktor[i]) manjifaktor[i]=1; // je prost
    }

    for(int i=2;i<=F;++i)
        if(manjifaktor[i]==1) kolicnik[i]=0; // prost
        else kolicnik[i]=inverz2[D[i]/D[manjifaktor[i]]];

    for(int i=2;i<=F;++i)
        if(manjifaktor[i]==1) sol[i]=1LL^i;
        else if(manjifaktor[i]==kolicnik[i]&&manjifaktor[kolicnik[i]]==1) sol[i]=1LL^D[i]^manjifaktor[i]; // kvadrat prostog
        else if(manjifaktor[i]!=manjifaktor[kolicnik[i]]) sol[i]=sol[manjifaktor[i]]^D[i]^sol[kolicnik[i]]^1LL; // nema kvadrate prostog broja
        else{
            long long Eu=Euklid(D[manjifaktor[i]],D[kolicnik[i]]);
            if(manjifaktor[D[i]/Eu]==manjifaktor[D[i]]){ // 8
                sol[i]=D[i]^sol[kolicnik[i]]^sol[inverz2[D[i]/kolicnik[i]]]^1LL;
            }else sol[i]=D[i]^sol[inverz2[Eu]]^sol[inverz2[D[i]/Eu]]; // kolicnik i prost broj nemaju zajednicke
        }


    for(int i=1;i<=F;++i)
        izlaz[inverz1[D[i]]]=sol[i];
    for(int i=1;i<=F;++i) printf("%lld ",izlaz[i]);

    return 0;
}