#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    int k;
    if (!(cin >> n >> k)) return 0;

    vector<ll> d(k);
    for (int i = 0; i < k; i++) {
        cin >> d[i];
    }

    if (n == 1) {
        cout << "1\n";
        return 0;
    }

    vector<ll> sorted_d = d;
    sort(sorted_d.begin(), sorted_d.end());

    vector<ll> primes;
    for (ll val : sorted_d) {
        if (val == 1) continue;
        bool is_p = true;
        for (ll p : primes) {
            if (val % p == 0) {
                is_p = false;
                break;
            }
        }
        if (is_p) {
            primes.push_back(val);
        }
    }

    map<ll, vector<ll>> memo;
    for (ll p : primes) {
        ll temp = n;
        int max_e = 0;
        while (temp % p == 0) {
            temp /= p;
            max_e++;
        }

        memo[p].push_back(1);
        ll curr = 1;
        ll xsum = 1;
        for (int i = 0; i < max_e; i++) {
            curr *= p;
            xsum ^= curr;
            memo[p].push_back(xsum);
        }
    }

    for (int i = 0; i < k; i++) {
        ll val = d[i];
        ll ans = 1;
        for (ll p : primes) {
            if (val == 1) break;
            if (val % p == 0) {
                int cnt = 0;
                while (val % p == 0) {
                    cnt++;
                    val /= p;
                }
                ans *= memo[p][cnt];
            }
        }
        cout << ans << (i == k - 1 ? "" : " ");
    }
    cout << "\n";

    return 0;
}