#include <bits/stdc++.h>
#include "ancient2.h"
using namespace std;
namespace Solver
{
	const int N=1e3+5,M=102;
	int n,r,fail[N];bitset<N> w,z[N],z1[N];pair<vector<int>,vector<int>> z2[N];
	void ins(bitset<N> a,pair<vector<int>,vector<int>> b)
	{
		if(r==n) return;bitset<N> a1;
		for(int i=0;i<n;++i) if(a[i])
		{if(z[i][i]) a^=z[i],a1^=z1[i];else {++r;a1[i]=1;z[i]=a;z1[i]=a1;z2[i]=b;break;}}
	}
	string Solve(int _n)
	{
		n=_n;string res(n,'0');
		for(int i=0;i<n;++i) if(i<M-2)
		{
			vector<int> b1(i+3),b2(i+3);
			for(int j=0;j<i;++j) b1[j]=b2[j]=j+1;
			b1[i]=b1[i+1]=b2[i+1]=i+1;b2[i]=b1[i+2]=b2[i+2]=i+2;
			++r;z[i][i]=z1[i][i]=1;w[i]=Query(b1.size(),b1,b2)==i+2;
		}
		for(int i=n-1;i>=0;--i) if(n-i<M)
		{
			vector<int> b1(n-i+1),b2(n-i+1);w[i]=1;fail[i]=i-1;
			for(int j=i+1,t=i-1;j<n;++j)
			{
				while(t>=i && w[j]!=w[t+1]) t=fail[t];
				t+=w[j]==w[t+1];fail[j]=t;
			}
			for(int j=i-1,t;j<n;++j)
			{
				t=j;while(t>=i && (t>=n-1 || w[t+1])) t=fail[t];
				b1[j-i+1]=t+(t<n-1 && !w[t+1])-i+1;
				t=j;while(t>=i && (t>=n-1 || !w[t+1])) t=fail[t];
				b2[j-i+1]=t+(t<n-1 && w[t+1])-i+1;
			}++r;z[i][i]=z1[i][i]=1;w[i]=Query(b1.size(),b1,b2)==n-i;
		}
		for(int i=1;i*2<=M;++i) for(int j=0;j<i;++j)
		{
			bitset<N> a=0;vector<int> b1(i*2),b2(i*2);for(int k=0;k<n;++k) a[k]=k%i==j;
			for(int k=0;k<i*2;++k) b1[k]=(k+2)%(i*2),b2[k]=(k+2)%(i*2)^(k/2==j);ins(a,{b1,b2});
		}for(int i=n-1;i>=0;--i) for(int j=i+1;j<n;++j) if(z[i][j]) z1[i]^=z1[j];
		for(int i=0;i<n;++i) if(!z2[i].first.empty())
			w[i]=Query(z2[i].first.size(),z2[i].first,z2[i].second)&1;
		for(int i=0;i<n;++i) res[i]=((z1[i]&w).count()&1)+'0';return res;
	}
}
string Solve(int n) {return Solver::Solve(n);}