#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
mt19937 rng(69);
int rnd(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
int qry(vector<int> v) {
int m = 2 * sz(v);
vector<int> a(m), b(m);
for (int i = 0; i < m; i++) {
int par = i % 2, c = i / 2;
a[i] = ((c + 1) % sz(v)) * 2 + par;
if (v[c]) {
b[i] = ((c + 1) % sz(v)) * 2 + (par ^ 1);
} else {
b[i] = a[i];
}
}
return Query(m, a, b) % 2;
}
string Solve(int N) {
const int p = 57;
const int n = 1e3;
assert(n == N);
bitset<n> b[n]; // basis
int who[n];
for (int i = 0; i < n; i++) b[i] = 0;
int cnt = 0;
while (cnt < n) {
int x = rnd(1, p);
vector<int> use(x);
for (int i = 0; i < x; i++) use[i] = rnd(0, 1);
bitset<n> cur;
int my_who = 0;
for (int i = 0; i < n; i++) cur[i] = use[i % x];
for (int i = 0; i < n; i++) if (cur[i]) {
if (b[i].any()) {
cur ^= b[i];
my_who ^= who[i];
} else {
b[i] = cur;
who[i] = my_who ^= qry(use);
cnt++;
break;
}
}
}
string s;
for (int i = 0; i < n; i++) {
int ans = 0;
bitset<n> cur; cur[i] = 1;
for (int j = 0; j < n; j++) if (cur[j]) {
cur ^= b[j];
ans ^= who[j];
}
s += char('0' + ans);
}
return s;
}
