#include <bits/stdc++.h>
#define fi first
#define sc second
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define pii pair<int,int>
using namespace std;
typedef long long ll;

#define int long long
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    vi a(k);
    for(int i = 0; i < k; i++) cin >> a[i];
    if(n <= 10000000){
        vi ans(n+1, 1);

        for(int i = 2; i <= n; i++){
            for(int j = i; j <= n; j+=i){
                ans[j] ^= i;
            }
        }

        for(int i = 0; i < k; i++){
            cout << ans[a[i]] << ' ';
        }
        cout << '\n';
    }
    else cout << ":)\n";
    return 0;
}