#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <cstring>
#include <string.h>
#include <sstream>
#include <iomanip>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <tuple>
#include <vector>
#include <random>
#include <chrono>
#include <stdio.h>
#include <stdlib.h>
#include "cave.h"
using namespace std;
#define F first
#define S second
#define siz(v) ((int)v.size())
#define rs(n) resize(n)
#define ALL(v) v.begin(),v.end()
#define reset(v) memset((v),0,sizeof(v))
#define EB emplace_back
#define MP make_pair
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define debug(x) cout << " > " << #x << ':' << x << endl;
#define kiyohime ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using vec = vector<T>;
template<typename T> using Prior = priority_queue<T>;
template<typename T> using prior = priority_queue<T, vec<T>, greater<T>>;
const int INF = 1e9;
const ll LLINF = (ll)4*1e18;
const ll MOD = 1e9+7;
const double PI = 3.14159265358;
const double EPS = 1e-8;
const int xx[8] = {0,1,0,-1,1,1,-1,-1};
const int yy[8] = {1,0,-1,0,1,-1,-1,1};
void pmod(ll &a, ll b) {a = (a+b)%MOD;}
void mmod(ll &a, ll b) {a = (a-b+MOD)%MOD;}
void tmod(ll &a, ll b) {a = (a*b)%MOD;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll POW(ll a, ll b) {ll res=1; do{if(b%2)tmod(res,a);tmod(a,a);}while(b>>=1); return res;}
template<typename T> void amax(T &a, T b) {if(a < b) a = b;}
template<typename T> void amin(T &a, T b) {if(a > b) a = b;}
void exploreCave(int n){
int pos[n], ans[n], l, r, tmp;
bool cur, vis[n];
rep(i, n) pos[i] = ans[i] = vis[i] = 0;
rep(i, n){
tmp = tryCombination(ans);
cur = (tmp > i || tmp == -1);
l = 0;
r = n;
while(r - l > 1){
int mid = (r + l) >> 1;
REP(j, l, mid-1)
if(!vis[j]) ans[j] = 1;
tmp = tryCombination(ans);
REP(j, l, mid-1)
if(!vis[j]) ans[j] = 0;
if(cur != (tmp > i || tmp == -1)) r = mid;
else l = mid;
}
pos[l] = i;
ans[l] = !cur;
vis[l] = true;
}
answer(ans, pos);
}
