#include "ancient2.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
int variable_example = 1;
} // namespace
// this is AI gen
vector<pair<int,int>> find_basis() {
const int N = 1000, MAXL = 57;
using Vec = bitset<N>;
// generate candidates
vector<pair<int,int>> candidates;
vector<Vec> candMask;
for (int L = 1; L <= MAXL; L++) {
for (int o = 0; o < L; o++) {
Vec v;
for (int p = o; p < N; p += L) v.set(p);
candidates.push_back({o, L});
candMask.push_back(v);
}
}
// shuffle
mt19937 g(42);
vector<int> order(candidates.size());
iota(order.begin(), order.end(), 0);
shuffle(order.begin(), order.end(), g);
// Gaussian elimination greedy
vector<pair<int,int>> chosen;
vector<Vec> basis(N); // basis vectors by pivot
for (int idx : order) {
Vec v = candMask[idx];
// reduce against current basis
for (int i = N-1; i >= 0; i--) {
if (v[i]) {
if (basis[i].any()) v ^= basis[i];
else {
basis[i] = v;
chosen.push_back(candidates[idx]);
break;
}
}
}
if ((int)chosen.size() == N) break;
}
// final check: did we get 1000 independent vectors?
if ((int)chosen.size() != N) chosen.clear();
return chosen;
}
// these not
int Xor(int n, int o) {
assert(o<n);
int m = n+n;
std::vector<int> a(m), b(m);
for (int i = 0; i < n; ++i) {
a[i] = i+1;
b[i] = i+1;
}
a[n-1] = 0; b[n-1] = 0;
for (int i = n; i < m; ++i) {
a[i] = i+1;
b[i] = i+1;
}
a[m-1] = n; b[m-1] = n;
std::swap(b[o], b[o+n]);
int r = Query(m, a, b);
return r >= n;
}
std::string Solve(int N) {
assert(1000==N);
std::vector<std::pair<int,int>> basis = find_basis();
std::vector<std::bitset<1001>> bs;
for (auto& [o, n] : basis) {
bs.emplace_back(std::bitset<1001>(0));
bs.back().reset();
for (int i = o; i < 1000; i += n) {
bs.back().set(i);
}
int a = Xor(n, o);
if (a) bs.back().set(1000);
}
std::vector where(1000, -1);
std::vector ans(1000, 0);
for (int c = 0, r = 0; c < 1000 && r < bs.size(); ++c) {
for (int i = r; i < bs.size(); ++i) {
if (bs[i][c]) {
swap(bs[i], bs[r]);
break;
}
}
if (!bs[r][c]) continue;
where[c] = r;
for (int i = 0; i < bs.size(); ++i) {
if (i != r && bs[i][c]) bs[i] ^= bs[r];
}
++r;
}
for (int i = 0; i < 1000; ++i) {
if (where[i] == -1) continue;
int r = where[i];
assert(0 <= r && r < bs.size());
if (bs[r].count() == 2) ans[i] = 1;
}
std::string s = "";
for (int i = 0; i < 1000; ++i) {
if (ans[i]) s += "1";
else s += "0";
}
return s;
}
