#include<bits/stdc++.h>
#include "ancient2.h"
using namespace std;
int an[1005];
int ss[1005],nxt[1005];
string Solve(int N){
	for(int i=1;i<=500;++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-500;--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]!=0)r=nxt[r];
				if(ss[r+1]==1)n0=r+1;
				else n0=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;
	}
	string st;
	for(int i=1;i<=N;++i)st+=an[i]+'0';
	return st;
}