// yukicoder: 97 最大の値を求めるくえり // 2019.8.17 bal4u #include #include typedef long long ll; #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() { // 整数の入力 int n = 0, c = gc(); do n = 10*n + (c & 0xf), c = gc(); while (c >= '0'); return n; } void out(int n) { // 正整数の表示(出力) int i; char b[20]; i = 0; while (n) b[i++] = n % 10 + '0', n /= 10; while (i--) pc(b[i]); pc('\n'); } unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned xor128() { unsigned t = x ^ (x << 11); x = y, y = z, z = w; return w = w ^ (w >> 19) ^ (t ^ (t >> 8)); } #define M 100003 #define MAX M int inv[MAX+10] = {1,1}; int a[MAX+10]; int N; int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } void generateA() { int i = N; while (i--) a[i] = (int)(xor128() % M); } int bs(int x) { int m, l = 0, r = N-1; while (l < r) { m = (l + r) >> 1; if (a[m] == x) return 1; if (a[m] < x) l = m + 1; else r = m; } return a[l] == x; } int main() { int i, Q, q, t, ans; for (i = 2; i <= MAX; i++) inv[i] = -(M/i)*(ll)inv[M % i] % M; N = in(), Q = in(); generateA(); if (N < 2000) { while (Q--) { q = in(); if (q == 0) { pc('0'), pc('\n'); continue; } ans = 0, i = N; while (i--) { t = (ll)q*a[i] % M; if (t > ans) ans = t; } out(ans); } return 0; } qsort(a, N, sizeof(int), cmp); while (Q--) { q = in(); if (q == 0) { pc('0'), pc('\n'); continue; } for (i = M-1; ; i--) { t = i * (ll)inv[q] % M; if (t < 0) t += M; if (bs(t)) { out(i); break; } } } return 0; }