#include <iostream>
#include <vector>
using namespace std;

const long long MOD=100003;
long long ind[MOD];

long long pow_mod(long long a,long long n) {
    return n!=0?pow_mod(a*a%MOD,n/2)*(n%2==1?a:1)%MOD:1;
}

unsigned xor128_x = 123456789, xor128_y = 362436069, xor128_z = 521288629, xor128_w = 88675123;
unsigned xor128() {
	unsigned t = xor128_x ^ (xor128_x << 11);
	xor128_x = xor128_y; xor128_y = xor128_z; xor128_z = xor128_w;
	return xor128_w = xor128_w ^ (xor128_w >> 19) ^ (t ^ (t >> 8));
}

vector<int> generateA(int N) {
  vector<int> A(N);
  for(int i = 0; i < N; ++ i)
    A[i] = xor128() % MOD;
  return A;
}

main() {
    int g=2;
    for (int i=0;i<MOD;++i) {
        ind[pow_mod(g,i)]=i;
    }
    
    int N,Q;
    cin>>N>>Q;
    bool ok[MOD];
    auto A=generateA(N);
    int sz=0;
    for (int i=0;i<MOD;++i) ok[i]=false;
    for (long long v:A) {
        if (v!=0) {
            ok[ind[v]]=true;
            ++sz;
        }
    }
    while (Q--) {
        int q;
        cin>>q;
        if (q==0) {
            cout<<0<<endl;
            continue;
        }
        int ind_q=ind[q];
        int ans=0;
        int ord=MOD-1;
        if (N>1000) {
            for (int i=MOD-1;i>=1;--i) {
                if (ok[(ind[i]-ind_q+ord)%ord]) {
                    ans=i;
                    break;
                }
            }
        } else {
            for (long long v:A) {
                ans=max(ans,(int)(v*q%MOD));
            }
        }
        cout<<ans<<endl;
    }
    
}