import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np MOD = 100003 N, _, *Q = map(int, read().split()) mask = (1 << 32) - 1 def generate_A(N): xor128_x = 123456789 xor128_y = 362436069 xor128_z = 521288629 xor128_w = 88675123 for _ in range(N): t = xor128_x ^ (xor128_x << 11) t &= mask xor128_x = xor128_y xor128_y = xor128_z xor128_z = xor128_w xor128_w = xor128_w ^ (xor128_w >> 19) ^ (t ^ (t >> 8)) xor128_w &= mask yield xor128_w % MOD A = np.array(list(generate_A(N)), np.int32) def strategy_1(A): answer = [0] * MOD S = np.zeros_like(A) for i in range(MOD): answer[i] = S.max() S += A S[S >= MOD] -= MOD return answer def strategy_2(A): answer = [0] * MOD isin_A = np.zeros(MOD, np.bool) isin_A[A] = 1 x = np.arange(99400, MOD) S = np.zeros_like(x) for i in range(1, MOD): inv = pow(i, MOD - 2, MOD) S += x S[S >= MOD] -= MOD answer[inv] = 99400 + np.where(isin_A[S])[0][-1] return answer if N < 2000: answer = strategy_1(A) else: answer = strategy_2(A) for q in Q: print(answer[q])