#ifdef __AVX2__
#pragma GCC target "avx2"
#endif
#pragma GCC optimize "O3"
#pragma GCC optimize "unroll-loops"
#include <bits/stdc++.h>
#include "cave.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// #define int long long
#define elif else if
#define all(l) begin(l),end(l)
#define rall(l) rbegin(l),rend(l)
#define append push_back
#define print(l) for(auto i:l) cout<<i<<' '; cout<<endl;
#define pprint(a,b) cout<<a<<' '<<b<<endl;
#define inp(l) for(auto &i:l) cin>>i;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pai make_pair
#define endl "\n"
#define pii pair<int,int>
#define fi first
#define se second
#define vec vector
// const int mod=998244353;
const int mod1=998244353;
const int mod=1e9+7;
// const int N=2e5+5;
void exploreCave(int n){
int sw[n],d[n];
for(int i=0;i<n;i++) sw[i]=d[i]=-1;
int qu[n];
int temp;
for(int i=0;i<n;i++){
int st=0;
for(int i=0;i<n;i++){
if(sw[i]>=0) qu[i]=sw[i];
else qu[i]=st;
}
temp=tryCombination(qu);
if(temp>i or temp==-1){}
else st=1-st;
int l=0,r=n;
// cout<<st<<endl;
while(l+1<r){
int m=(l+r-1)/2;
for(int j=0;j<n;j++){
if(sw[j]>-1) qu[j]=sw[j];
elif(j>=l and j<=m) qu[j]=st;
else qu[j]=1-st;
}
// cout<<i<<' '<<l<<' '<<r<<' '<<m<<endl;
// print(qu)
// cout<<endl;
int temp=tryCombination(qu);
if(temp>i or temp==-1) r=m+1;
else l=m+1;
}
// cout<<i<<' '<<l<<' '<<st<<endl;
sw[l]=st;
d[l]=i;
}
answer(sw,d);
}
