#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'
vector<int> prefix_function(string s){
int n = sz(s);
vector<int> pi(n);
for (int i = 1; i < n; i++){
int k = pi[i - 1];
while (k && s[k] != s[i]) k = pi[k - 1];
pi[i] = k + (s[i] == s[k]);
}
return pi;
}
vector<vector<int>> build_automaton(string s){
auto pi = prefix_function(s);
int n = sz(s);
vector<vector<int>> aut(2, vector<int>(n + 1));
for (int i = 0; i <= n; i++){
for (int c = 0; c < 2; c++){
if (s[i] == '0' + c) aut[c][i] = i + 1;
else if (i) aut[c][i] = aut[c][pi[i - 1]];
}
}
return aut;
}
std::string Solve(int n) {
int half1 = n / 2, half2 = n - half1;
string s, t;
for (int i = 0; i < half1; i++){
vector<int> a(i + 3), b(i + 3);
iota(all(a), 1);
iota(all(b), 1);
a[i] = i + 1, b[i] = i + 2;
a[i + 1] = b[i + 1] = i + 1;
a[i + 2] = b[i + 2] = i + 2;
s.pb(Query(sz(a), a, b) == i + 1? '0' : '1');
}
for (int i = 0; i < half2; i++){
auto aut = build_automaton("0" + t);
t = (Query(sz(aut[0]), aut[0], aut[1]) == sz(t) + 1? "0" : "1") + t;
}
return s + t;
}
