#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'
const int N = 1000;
bitset<N> basisx[N], basisy[N];
bool res[N], val[N];
vector<pair<int, int>> pairs;
void try_add(int q, int p){
bitset<N> curx, cury;
for (int i = q; i < N; i += p) curx.set(i);
for (int i = N - 1; i >= 0; i--){
if (!curx.test(i)) continue;
if (!basisx[i].any()){
cury.set(sz(pairs));
pairs.pb({q, p});
basisx[i] = curx, basisy[i] = cury;
return;
}
curx ^= basisx[i], cury ^= basisy[i];
}
}
void precalc(){
for (int p = 1;; p++){
for (int q = 0; q < p; q++){
try_add(q, p);
if (sz(pairs) == N) return;
}
}
}
std::string Solve(int n) {
precalc();
for (int i = 0; i < N; i++){
auto [q, p] = pairs[i];
vector<int> a(2 * p), b(2 * p);
iota(all(a), 1);
iota(all(b), 1);
a[p - 1] = 0, a[2 * p - 1] = p;
b[p - 1] = 0, b[2 * p - 1] = p;
b[q] = p + (q + 1) % p, b[p + q] = (q + 1) % p;
res[i] = (Query(2 * p, a, b) >= p);
}
string ans;
for (int i = 0; i < n; i++){
for (int j = 0; j < N; j++){
if (basisy[i].test(j)) val[i] ^= res[j];
if (j < i && basisx[i].test(j)) val[i] ^= val[j];
}
ans.pb('0' + val[i]);
}
return ans;
}
