#include<bits/stdc++.h>
#include "ancient2.h"
using namespace std;
int an[1005];
int ss[1005],nxt[1005];
bitset<1005>e[1005];
int ee[1005];
string Solve(int N){
	for(int i=1;i<=1000;++i)e[i].reset(),ee[i]=0;
	for(int i=1;i<=100;++i){
		vector<int>A;
		vector<int>B;
		for(int j=0;j<i-1;++j){
			A.emplace_back(j+1);
			B.emplace_back(j+1);
		}
		A.emplace_back(i);B.emplace_back(i+1);
		A.emplace_back(i);B.emplace_back(i);
		A.emplace_back(i+1);B.emplace_back(i+1);
		int x=Query(i+2,A,B);
		if(x==i)an[i]=0;
		else an[i]=1;
	}
	for(int i=N;i>N-100;--i){
		int l=N-i+1;
		for(int j=1;j<=l;++j){
			if(j==1)ss[j]=0;
			else ss[j]=an[i+j-1];
		}
		nxt[1]=0;
		for(int j=2;j<=l;++j){
			int r=nxt[j-1];
			while(r&&ss[r+1]!=ss[j])r=nxt[r];
			if(ss[r+1]==ss[j])nxt[j]=r+1;
			else nxt[j]=0;
		}
		vector<int>A,B;
		for(int j=0;j<=l;++j){
			int n0=0,n1=0;
			if(j<l&&ss[j+1]==0)n0=j+1;
			else{
				int r=nxt[j];
				while(r&&ss[r+1]!=0)r=nxt[r];
				if(ss[r+1]==0)n0=r+1;
				else n0=0;
			}
			if(j<l&&ss[j+1]==1)n1=j+1;
			else{
				int r=nxt[j];
				while(r&&ss[r+1]!=1)r=nxt[r];
				if(ss[r+1]==1)n1=r+1;
				else n1=0;
			}
			A.emplace_back(n0);
			B.emplace_back(n1);
		}
		int x=Query(l+1,A,B);
		if(x==l)an[i]=0;
		else an[i]=1;
	}
	for(int p=1;p<=51;++p)for(int q=0;q<p;++q){
		bitset<1005>bs;
		for(int i=1;i<=N;++i)if(i>100&&i<=N-100&&(i-1)%p==q)bs.set(i);
		int yh=0,wz=0;
		for(int i=1;i<=N;++i)if(i<=100||i>N-100)
			if((i-1)%p==q)yh^=an[i];
		for(int i=N;i>=1;--i)if(bs[i]){
			if(!ee[i]){
				wz=i;
				break;
			}
			bs^=e[i];yh^=(ee[i]==1?1:0);
		}
		if(wz){
			vector<int>A(2*p),B(2*p);
			for(int i=0;i<p;++i)A[i]=B[i]=(i+1)%p;
			for(int i=p;i<2*p;++i)A[i]=B[i]=(i+1)%p+p;
			swap(B[q],B[q+p]);
			int x=Query(2*p,A,B);
			if(x>=p)yh^=1;
		}
		e[wz]=bs;ee[wz]=(yh==1?1:-1);
	}
	for(int i=101;i<=N-100;++i){
		bitset<1005>bs;
		bs[i]=1;
		int yh=0;
		for(int i=N;i>=1;--i)if(bs[i]){
			bs^=e[i];yh^=(ee[i]==1?1:0);
		}
		an[i]=yh;
	}
	string st;
	for(int i=1;i<=N;++i)st+=an[i]+'0';
	return st;
}