/* upsolved with help from GusterGoose27 */
#include "ancient2.h"
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ull;
typedef vector<int> vi;
const int N = 1000, M = 102, L = 64, K = (N + L - 1) / L;
ull vvv[N][K]; int ww[N];
int add(ull *vv) {
int w = 0;
for (int i = 0; i < N; i++)
if ((vv[i / L] & 1ULL << i % L) != 0) {
if ((vvv[i][i / L] & 1ULL << i % L) != 0) {
for (int h = i / L; h < K; h++)
vv[h] ^= vvv[i][h];
w ^= ww[i];
} else {
for (int h = i / L; h < K; h++)
vvv[i][h] = vv[h];
ww[i] = w;
return i;
}
}
return -1;
}
string Solve(int n) {
string cc(N, '0');
ull vv[K];
int rank = 0;
for (int i = 0; i + 3 <= M; i++) {
memset(vv, 0, K * sizeof *vv), vv[i / L] |= 1ULL << i % L;
add(vv), rank++;
int m = i + 3;
vi aa(m), bb(m);
for (int s = 0; s < i; s++)
aa[s] = bb[s] = s + 1;
aa[i] = i + 1, bb[i] = i + 2;
aa[i + 1] = bb[i + 1] = i + 1;
aa[i + 2] = bb[i + 2] = i + 2;
if (Query(m, aa, bb) != i + 1)
ww[i] ^= 1;
}
for (int i = N - 1; N - i + 1 <= M; i--) {
memset(vv, 0, K * sizeof *vv), vv[i / L] |= 1ULL << i % L;
add(vv), rank++;
cc[i] = '0';
int m = N - i + 1;
vi aa(m), bb(m);
int f = -1;
for (int s = 0; s + 1 < m; s++) {
if (cc[i + s] == '0')
aa[s] = s + 1, bb[s] = f == -1 ? 0 : bb[f];
else
aa[s] = f == -1 ? 0 : aa[f], bb[s] = s + 1;
f = f == -1 ? 0 : (cc[i + s] == '0' ? aa[f] : bb[f]);
}
aa[m - 1] = aa[f], bb[m - 1] = bb[f];
if (Query(m, aa, bb) != m - 1)
ww[i] ^= 1, cc[i] = '1';
}
for (int c = 1; c * 2 <= M; c++) {
int m = c * 2;
vi aa(m), bb(m);
for (int r = 0; r < c; r++) {
memset(vv, 0, K * sizeof *vv);
for (int i = 0; i < N; i++)
if (i % c == r)
vv[i / L] |= 1ULL << i % L;
int i = add(vv);
if (i != -1) {
rank++;
for (int s = 0; s < c; s++) {
aa[s] = bb[s] = (s + 1) % c;
aa[c + s] = bb[c + s] = c + (s + 1) % c;
}
bb[r] = c + (r + 1) % c;
bb[c + r] = (r + 1) % c;
if (Query(m, aa, bb) >= c)
ww[i] ^= 1;
}
}
}
if (rank != N)
return ":(";
for (int i = N - 1; i >= 0; i--) {
for (int j = i + 1; j < N; j++)
if ((vvv[i][j / L] & 1ULL << j % L) != 0)
ww[i] ^= ww[j];
cc[i] = ww[i] + '0';
}
return cc;
}
