#include <bits/stdc++.h>
// #include "grader.c"
#include "cave.h"
using namespace std;
#define cin(vec) for(auto& i : vec) cin >> i
#define cout(vec) for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b) for (int i = a; i < b; i++)
#define F first
#define S second
#define pb(n) push_back(n)
#define pf(n) push_front(n)
#define dci(d) fixed<<setprecision(d)
#define sp ' '
#define el '\n'
#define all(v) v.begin(),v.end()
// #define int long long
#define try tryCombination
int vis[5001],loc[5001];
void exploreCave(int n) {
int swich[n]={};
int doors[n];
memset(doors,-1,sizeof doors);
memset(vis,-1,sizeof vis);
memset(loc,-1,sizeof loc);
while(1){
int x=try(swich);
if(x==-1){
break;
}
if(~loc[x]&&~vis[loc[x]]){
swich[loc[x]]^=1;
continue;
}
for(int i=0;i<n;i++){
swich[i]^=1;
int y=try(swich);
if(y>x||y==-1){
doors[i]=x;
break;
}
doors[i]=y;
vis[i]=swich[i];
loc[y]=i;
swich[i]^=1;
}
}
for(int i=0;i<n;i++){
swich[i]^=1;
int x=try(swich);
// cout<<x<<' ';
doors[i]=x;
swich[i]^=1;
}
answer(swich,doors);
}
