#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

#define int int64_t

int get2(int z, int k) {
    z %= (1ll << k);
    if (k == 0) return 1;
    if (k == 1) return 2;
    if (k == 2) {
        if (z == 0) return 4;
        if (z == 1) return 8;
        if (z == 2) return 4;
        return 0;
    }
    if (z % 4 == 0) {
        return get2(z / 4, k - 2) * 4;
    }
    if (z % 8 == 2 || z % 8 == 1 || z % 8 == 5) {
        return (1ll << (k + 1));
    }
    return 0;
}

int getp(int z, int p) {
    z %= p;
    int x = -1;
    int res = 1;
    int n = (p - 1) / 2;
    while (n) {
        if (n % 2 == 0) {
            x *= x;
            n /= 2;
        } else {
            res *= x;
            n--;
        }
    }
    if (z == 0) {
        if (res == 1) {
            return 2 * p - 1;
        } else {
            return 1;
        }
    }
    return p - res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int m, n;
    cin >> m >> n;
    for (int i = 0; i < n; ++i) {
        int z;
        cin >> z;
        int ans = 1;
        int m1 = m;
        int k = 0;
        while (m % 2 == 0) {
            m /= 2;
            ++k;
        }
        ans *= get2(z, k);
        for (int p = 3; p * p <= m; ++p) {
            if (m % p == 0) {
                m /= p;
                ans *= getp(z, p);
                while (m % p == 0) {
                    m /= p;
                    ans *= p;
                }
            }
        }
        if (m != 1) {
            ans *= getp(z, m);
        }
        m = m1;
        cout << ans << " ";
    }
    cout << "\n";

    return 0;
}