import sys
input = sys.stdin.readline

N,Q=map(int,input().split())

mod=100003

xor128_x = 123456789
xor128_y = 362436069
xor128_z = 521288629
xor128_w = 88675123

def xor128():
    global xor128_x, xor128_y, xor128_z, xor128_w
    t = xor128_x ^ ((xor128_x << 11) & 0xffffffff)
    xor128_x = xor128_y
    xor128_y = xor128_z
    xor128_z = xor128_w
    xor128_w = xor128_w ^ ((xor128_w >> 19) & 0xffffffff) ^ (t ^ ((t >> 8) & 0xffffffff))
    xor128_w &= 0xffffffff  # 32bitに制限
    return xor128_w

def generateA(N):
    A = [0] * N
    for i in range(N):
        A[i] = xor128() % 100003
    return A

A = generateA(N)
SET=set(A)

for tests in range(Q):
    x=int(input())

    if x==0:
        print(0)
    elif N<=500:
        ANS=0
        for a in A:
            ANS=max(ANS,a*x%mod)

        print(ANS)
    else:
        INV=pow(x,mod-2,mod)
        for i in range(mod-1,-1,-1):
            k=i*INV%mod

            if k in SET:
                ANS=i
                break

        print(ANS)