#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))

const int MOD = 100003;
const int MAX = 100003;
int N, Q;
int inv[MOD];
int res[MOD];
int A[MAX];
bool exist[MOD];

unsigned int xor128(void) {
    static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned int t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

void init(int N){
    // ( (inv[i] * i) % MOD == 1) となる配列
    inv[0] = 0; inv[1] = 1;
    for(int i = 2; i < MOD; i++){
        inv[i] = (ll)inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
    REP(i,N) A[i] = xor128() % MOD, exist[A[i]] = true;
    memset(res, -1, sizeof(res));
    res[0] = 0;
}
int solve(int q){
    if(res[q] >= 0) return res[q];
    // 最大がmxになるようなAがあるか調べる
    for(int mx = MOD-1; mx > MOD-1000; mx--){
        if(exist[(ll)mx * inv[q] % MOD]){
            return res[q] = mx;
        }
    }
    // 1000個調べても無かったら総当り
    int mx = 0;
    REP(i,N) mx = max(mx, (int)((ll)q * A[i] % MOD));
    return res[q] = mx;
}

int main(){
    cin >> N >> Q;
    init(N);

    REP(i,Q){
        int q; cin >> q;
        cout << solve(q) << endl;
    }
    return 0;
}