#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
const int N=5e3 +10;
const int mod=1e9 + 7;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl
//Trace prints the name of the variable and the value.
int n;int cur[N], match[N], ans[N];//match is D answer function ka. cur will be S.
bool change[N];
void exploreCave(int NC)
{
n=NC;
for(int i=0;i<n;i++)
{
change[i]=1;cur[i]=0;
}
for(int i=0;i<n;i++)
{
int ret=tryCombination(cur);int corr;
if(ret==i) corr=1;
else corr=0;
int low=0, high=n-1;
while(high-low>1)
{
int mid=(low+high)/2;
for(int j=low;j<=mid;j++)
cur[j]^=change[j];
ret=tryCombination(cur);
if(corr==0)
{
if(ret>i||ret==-1) low=mid+1;
else high=mid;
}
else
{
if(ret>i||ret==-1) high=mid;
else low=mid+1;
}
for(int j=low;j<=mid;j++)
if(change[j]) cur[j]=0;
}
if(corr==1)
{
cur[high]^=change[high];ret=tryCombination(cur);
if(ret>i||ret==-1) {low=high;}
}
else
{
cur[high]^=change[high];ret=tryCombination(cur);
if(ret==i) {low=high;}
}
change[low]=0;cur[low]=corr;match[low]=i;
for(int j=0;j<n;j++)
if(change[j]) cur[j]=0;
}
answer(cur, match);
}
