#include<bits/stdc++.h>
#include "cave.h"
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll dor[50005],fix[40005],kon[40005],ans[40005];
ll ind,that,h,f,n;
int v[5000];
//tryCombination
void go(ll x,ll y){
if(x == y){
ans[ind] = x;
return;
}
for(int i=x; i <= (x + y) / 2; i++)
if(fix[i] != 1)
v[i] ^= 1;
// cout << ind << " " << x << " " << y << endl;
int h = tryCombination(v);
// cout << "Got " << h << endl;
for(int i=x; i <= (x + y) / 2; i++)
if(fix[i] != 1)
v[i] ^= 1;
if(h == -1){
h = 5000;
}
for(int i=1; i<=n; i++){
}
if(h > ind){
go(x , (x + y) / 2);
}
else {
go((x + y) / 2 + 1 , y);
}
}
void exploreCave(int n){
for(int i=0; i<n; i++){
ind = i;
for(int j=0; j<n; j++)
if(fix[j] == 0)
v[j] = 0;
else
v[j] = kon[j];
int f = tryCombination(v);
if(f == -1)
f = n;
if(f > i){
that = 0;
for(int j=0; j<n; j++)
if(fix[j] == 0)
v[j] = 1;
else
v[j] = kon[j];
}
if(f == i)
that = 1;
go(0 , n - 1);
// cout << ans[ind] << " " << that << endl;
fix[ans[i]] = 1;
dor[ans[i]] = i;
kon[ans[i]] = that;
}
int s[n],d[n];
for(int i=0; i<n; i++)
d[i] = kon[i];
for(int i=0; i<n; i++)
s[i] = dor[i];
answer(d , s);
}
