d=1;h=[z=0]*M=9973;50000.times{print h[z=(z+d*=t=1942+2798*h[z]^=1)%M];d=d*t%M}