#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 1001;
const int MAXP = 51;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
namespace {
int n;
bool findPrefix(int p) {
int m = p + 3;
vi a(m);
iota(ALL(a), 1);
a[p + 1] = p + 1;
a[p + 2] = p + 2;
vi b = a;
a[p] = p + 1;
b[p] = p + 2;
int r = Query(m, a, b);
return r == p + 2;
}
bool findSuffix(string s) {
s = "1" + s;
int n = SZ(s);
s += "?";
int m = n + 1;
vi a(m), b(m);
string ps = "";
REP (i, 0, n + 1) {
auto get = [&] (char c) {
string ts = ps + c;
REP (j, 0, SZ(ts)) {
bool pos = 1;
REP (k, 0, SZ(ts) - j) {
if (ts[j + k] != s[k]) {
pos = 0;
}
}
if (pos) {
return SZ(ts) - j;
}
}
return 0;
};
a[i] = get('0');
b[i] = get('1');
ps += s[i];
}
int r = Query(m, a, b);
return r == m - 1;
}
bool findPeriod(int p, int q) {
int m = p + p;
vi a(m);
iota(a.begin(), a.begin() + p, 1);
iota(a.begin() + p, a.begin() + m, p + 1);
a[p - 1] = 0;
a[m - 1] = p;
vi b = a;
b[q] += p;
b[q + p] -= p;
int r = Query(m, a, b);
return r >= p;
}
bitset<MAXN> basis[MAXN];
bool insert(bitset<MAXN> bs) {
REP (i, 0, MAXN) {
if (!bs[i]) {
continue;
}
if (basis[i].none()) {
basis[i] = bs;
return 1;
}
bs ^= basis[i];
}
return 0;
}
int query(bitset<MAXN> bs) {
REP (i, 0, n) {
if (!bs[i]) {
continue;
}
if (basis[i].none()) {
return -1;
}
bs ^= basis[i];
}
return bs[n];
}
}
string Solve(int N) {
n = N;
string ans(n, '0');
int rem = 1000;
REP (i, 0, min(n, 100)) {
rem--;
ans[i] = findPrefix(i) + '0';
bitset<MAXN> bs;
bs[i] = 1;
bs[n] = ans[i] - '0';
insert(bs);
}
string suf = "";
RREP (i, n - 1, max(n - 101, 1)) {
rem--;
ans[i] = findSuffix(suf) + '0';
suf = ans[i] + suf;
bitset<MAXN> bs;
bs[i] = 1;
bs[n] = ans[i] - '0';
insert(bs);
}
REP (_, 0, rem) {
int p = rnd() % MAXP + 1, q = rnd() % p;
bitset<MAXN> bs;
while (1) {
bs.reset();
for (int j = q; j < n; j += p) {
bs[j] = 1;
}
if (query(bs) == -1) {
break;
}
p = rnd() % MAXP + 1, q = rnd() % p;
}
bool b = findPeriod(p, q);
bs[n] = b;
insert(bs);
}
REP (i, min(n, 100), max(n - 101, 1)) {
bitset<MAXN> bs;
bs[i] = 1;
ans[i] = query(bs) + '0';
}
return ans;
}
