#include "ancient2.h"
#include<bits/stdc++.h>
using namespace std;
string solve_left(int n){
string ans(n,'0');
int m=n+2;
vector<int> a(m),b(m);
a[n]=b[n]=n;
a[n+1]=b[n+1]=n+1;
for(int i=0;i<n;i++){
a[i]=n;
b[i]=n+1;
}
for(int i=0;i<n;i++){
int res=Query(m,a,b);
ans[i]=res-n+'0';
a[i]=b[i]=i+1;
}
return ans;
}
string solve_right(int n){
string ans(n,'0');
vector<bool> suf;
for(int i=1;i<=n;i++){
suf.insert(suf.begin(),1);
int m=i+1;
vector<vector<int>> a(2,vector<int>(m));
for(int j=0;j<m;j++){
for(int c=0;c<2;c++){
int sz=min(j+1,i);
auto sub1=[&](bool x){
vector<bool> res(suf.begin()+j-sz+1,suf.begin()+j);
res.emplace_back(x);
return res;
};
auto sub2=[&](){
return vector<bool>(suf.begin(),suf.begin()+sz);
};
while(sz>0&&sub1(c)!=sub2())sz--;
a[c][j]=sz;
}
}
int res=Query(m,a[0],a[1])==i;
ans[n-i]=res+'0';
suf[0]=res;
}
return ans;
}
string Solve(int n) {
return solve_left(n/2)+solve_right((n+1)/2);
}
