import sys
MOD = 100003

def xor128():
    global xor128_x, xor128_y, xor128_z, xor128_w
    t = xor128_x ^ ((xor128_x << 11) & 0xFFFFFFFF)
    t ^= (t >> 8)
    xor128_x, xor128_y, xor128_z = xor128_y, xor128_z, xor128_w
    new_w = (xor128_w ^ ((xor128_w >> 19) & 0xFFFFFFFF)) ^ t
    new_w &= 0xFFFFFFFF
    xor128_w = new_w
    return xor128_w

def generateA(N):
    A = []
    for _ in range(N):
        val = xor128() % MOD
        A.append(val)
    return A

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, Q = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    queries = [int(input[ptr+i]) for i in range(Q)]
    # Initialize xor128 state
    global xor128_x, xor128_y, xor128_z, xor128_w
    xor128_x, xor128_y, xor128_z, xor128_w = 123456789, 362436069, 521288629, 88675123
    # Generate array A
    A = generateA(N)
    # Preprocess exist array
    exist = [False] * MOD
    for a in A:
        exist[a] = True
    # Process queries
    for q in queries:
        if q ==0:
            print(0)
            continue
        inv_q = pow(q, MOD-2, MOD)
        found = -1
        for k in range(MOD-1, -1, -1):
            target_a = (k * inv_q) % MOD
            if exist[target_a]:
                found = k
                break
        print(found)

if __name__ == '__main__':
    main()