#include <bits/stdc++.h>
#include "ancient2.h"
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
namespace {
string FIRST() {
return (Query(3, {1, 1, 2}, {2, 1, 2}) == 1 ? "0" : "1");
}
pair<vector<int>, vector<int>> COMPRESS(string s) {
vector<int> a, b;
int n = s.size(), id = 0;
while (id < n) {
if (id == n - 1) {
a.push_back(a.size() + (s[id] == '0'));
b.push_back(b.size() + (s[id] == '1'));
id++;
} else {
int r = id;
while (s[r] == s[id]) r++;
a.push_back(a.size() + (s[id] == '1'));
b.push_back(b.size() + (s[id] == '0'));
id = r + 1;
}
}
return mp(a, b);
}
int Q1(vector<int> a, vector<int> b, bool INV) {
vector<int> va = {1, 2, 3, 3, 4, 5, 6, 7};
vector<int> vb = {4, 5, 6, 7, 4, 5, 6, 7};
int m = a.size();
for (auto &i : va) a.push_back(i + m);
for (auto &i : vb) b.push_back(i + m);
// debug(INV);
// for (auto &i : a) cout << i << ' ';
// cout << endl;
// for (auto &i : b) cout << i << ' ';
// cout << endl;
int res = (INV ? Query(m + 8, b, a) : Query(m + 8, a, b));
// debug();
if (res == m + 7) return -1;
return max(0, res - m - 3);
}
int GROUP(vector<int> a, vector<int> b, int G, bool INV) {
vector<int> va, vb;
FOR(i, 0, G - 1) va.push_back(i + 1);
va.push_back(0);
FOR(i, 0, G) va.push_back(i + G);
FOR(i, 0, G) vb.push_back(i + G);
FOR(i, 0, G) vb.push_back(i + G);
int m = a.size();
for (auto &i : va) a.push_back(i + m);
for (auto &i : vb) b.push_back(i + m);
int res = (INV ? Query(m + G * 2, b, a) : Query(m + G * 2, a, b));
return res - m - G;
}
int CRT(vector<int> a, vector<int> b, bool INV) {
int x = GROUP(a, b, 7, INV);
int y = GROUP(a, b, 11, INV);
int z = GROUP(a, b, 13, INV);
return (715 * x + 364 * y + 924 * z) % 1001;
}
string GET(vector<int> &a, vector<int> &b, char c) {
if (c & 1) swap(a, b);
int res = Q1(a, b, c & 1);
// debug(res);
if (res != -1) {
if (res == 0) return string(1005, c);
string ans;
ans = string(res - 1, c);
ans.push_back(c ^ 1);
return ans;
}
res = CRT(a, b, c & 1);
string ans = string(res, c);
ans.push_back(c ^ 1);
return ans;
}
string miku(int n) {
string ans = FIRST();
while (ans.size() < n) {
auto [va, vb] = COMPRESS(ans);
// debug(ans);
// for (auto &i : va) cout << i << ' ';
// cout << endl;
// for (auto &i : vb) cout << i << ' ';
// cout << endl;
string s = GET(va, vb, ans.back());
// ans.pop_back();
ans += s;
while (ans.size() > n) ans.pop_back();
debug(ans);
}
debug(ans);
return ans;
}
}
string Solve(int n) {
return miku(n);
}
