#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
// int ab (int x ) { return (x>0?x:-x); }
int n ,reply;
int cnt = 0 ;
int door[5005],Comb[5005];
int TryCombination(int S[]){
cnt++;
return tryCombination(S);
// for(int i = 0 ; i < n ; i++ )cout << S[i]; cout << endl;
// int answer ;
// cin >> answer;
// return answer;
}
void rev(int l , int r ){
for(int i = l ; i <= r ; i++ )if( door[i]==-1)Comb[i]=!Comb[i];
}
void exploreCave(int N){
n = N ;
memset(door,-1,sizeof door);
memset(Comb,0,sizeof Comb);
for(int T = 0 ; T < N ; T++ ){
// cerr <<"first try "<<endl;
int FI = TryCombination(Comb);
reply = FI ;
if( reply == -1 )break ;
int l = 0 , r =N-1 ;
while ( r-l>0){
int mid = (l+r)/2;
rev(l,mid);
// cerr <<"mid is "<<mid << endl;
reply = TryCombination(Comb);
if( reply == -1 )break;
rev(l,mid);
if( reply == FI && mid == l ){
// ans is r
Comb[r]=!Comb[r];
// cerr <<"found door of "<<r<<" is "<<reply<<" correct ans is " << Comb[r]<<endl;
door[r] = reply;
break ;
}else if( reply != FI && mid == l ){
Comb[l]=!Comb[l];
// cerr <<"found door of "<<r<<" is "<<reply<<" correct ans is " << Comb[r]<<endl;
door[l]=reply;
break;
}
if( reply == FI )l = mid ;
else r = mid ;
}
if( reply == -1 )break ;
// assert(reply == -1 || l == r );
// if( l == r )door[l]=reply;
}
assert(TryCombination(Comb)==-1);
for(int i = 0 ; i < n ; i++ )if( door[i]==-1 ){
rev(i,i);
reply = TryCombination(Comb);
rev(i,i);
door[i]=reply;
}
answer(Comb,door);
// for(int i = 0; i < n ; i++ )cerr << Comb[i]; cerr << endl;
// for(int i =0 ;i < n ;i++ )cerr << door[i] ; cerr <<endl;
}
// int main(){
// cin >> n ;
// exploreCave(n);
// }
