#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
#define pii pair<int,int>

using namespace std;

int euclid(int a, int b){
    if(a<b)swap(a,b);
    if(b==0ll)return a;
    return euclid(a%b,b);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n,k;
    cin>>n>>k;
    vector<pii> v(k);
    for(int i=0;i<k;i++){
        cin>>v[i].fi;
        v[i].se=i;
    }
    sort(v.begin(),v.end());
    vector<int> ans(k);
    map<int,int> m;
    m[1ll]=1ll;
    vector<int> p;
    vector<int> pdel;
    for(int i=1;i<k;i++){
        pdel.clear();
        for(auto a:p){
            if(v[i].fi%a==0ll)pdel.push_back(a);
        }
        if(pdel.size()==0ll){
            p.push_back(v[i].fi);
            m[v[i].fi]=v[i].fi^1ll;
        }
        else if( pdel.size()==1ll){
            m[v[i].fi]=v[i].fi^m[v[i].fi/pdel[0]];
        }
        else{
            m[v[i].fi]=v[i].fi^m[v[i].fi/pdel[0]]^m[v[i].fi/pdel[1]]^m[euclid(v[i].fi/pdel[0],v[i].fi/pdel[1])];
        }
    }

    for(int i=0;i<k;i++){
        ans[v[i].se]=m[v[i].fi ];
    }
    for(int i=0;i<k;i++)cout<<ans[i]<<' ';
    cout<<endl;

    return 0;
}