a=[123456789,362436069,521288629,88675123]
A=->{t=a[0]^a[0]<<11
a.shift
a+=[w=a[-1]^(a[-1]>>19)^t^t>>8]
w}
d=100003
N,Q,*q=$<.read.split.map &:to_i
r=N.times.map{A[]%d}
Q.times{|i|p n.times{|j|r[j]*q[i]%d}.max}