/* upsolved with help from GusterGoose27 */
#include "ancient2.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 1000;
string Solve(int n) {
string cc(N, 0);
for (int i = 0; i < N / 2; i++) {
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;
cc[i] = Query(m, aa, bb) == i + 1 ? '0' : '1';
}
for (int i = N - 1; i >= N / 2; i--) {
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)
cc[i] = '1';
}
return cc;
}
