#include "ancient2.h"
#include<bits/stdc++.h>
using namespace std;
bool prefix(int k){
int m = k+1+2;
vector<int>a(m), b(m);
for(int i=0;i<k;i++){
a[i] = i+1;
b[i] = i+1;
}
a[k] = k+1;
b[k] = k+2;
a[k+2] = k+2;
b[k+2] = k+2;
a[k+1] = k+1;
b[k+1] = k+1;
return Query(m,a,b)==(k+2);
}
string PoznajSufix(int k){
string s="2";
while((int)s.size()-1<k){
s[0]='0';
s = '2' + s;
int m = s.size();
vector<int>a(m), b(m);
vector<int>kmp(m);
kmp[0] = 0;
kmp[1] = 0;
for(int i=2;i<m;i++){
int j = kmp[i-1];
while(j!=0 && s[j+1]!=s[i])
j = kmp[j];
if(s[j+1]==s[i])
j++;
kmp[i] = j;
}
for(int i=0;i<m-1;i++){
if(s[i+1]=='0'){
a[i] = i+1;
int j = kmp[i];
while(s[j+1]!='1' && j!=0)j = kmp[j];
if(s[j+1]=='1')j++;
b[i] = j;
}
else if(s[i+1]=='1'){
int j = kmp[i];
while(s[j+1]!='0' && j!=0)j = kmp[j];
if(s[j+1]=='0')j++;
a[i] = j;
b[i] = i+1;
}
}
int j = kmp[m-1];
while(s[j+1]!='0' && j!=0)j = kmp[j];
if(s[j+1]=='0')j++;
a[m-1] = j;
j = kmp[m-1];
while(s[j+1]!='1' && j!=0)j = kmp[j];
if(s[j+1]=='1')j++;
b[m-1] = j;
if(Query(m, a, b)!=m-1)
s[1] = '1';
}
reverse(s.begin(), s.end());s.pop_back();reverse(s.begin(), s.end());
return s;
}
string Solve(int N) {
string s;
while((int)s.size()<N/2){
s.push_back('0'+prefix(s.size()));
}
string sufix;
sufix = PoznajSufix((N+1)/2);
// cout<<sufix<<"\n";
return s+sufix;
}
