#include "cave.h"
#include<bits/stdc++.h>
#define fori(a,b,c) for(int a=b; a<c; a++)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n;
int sw[5000];
int used[5000];
pii b[8900];
//pii a[8900];
int s[5000],d[5000];
void exploreCave(int N) {
n=N;
int lg=0;
while((1<<lg) < n){
lg++;
}
//cout << lg;
int nn=(1<<lg);
fori(i,0,n){
int las=0;
fori(j,0,lg+1){
fori(k,las,las+(nn/(1<<j))){
if(k>=n)
break;
if(!used[k]){
sw[k]=(b[i].se+1)%2;
}
else{
sw[k]=s[k];
}
}
if(las>=n){
continue;
}
int trc=tryCombination(sw);
if(n==1){
if(trc!=i){
b[i].se=1;
}
d[i]=i;
s[i]=b[i].se;
}
if(j==lg){
if(trc!=i){
used[las+1]=1;
b[i].fi=las+1;
d[las+1]=i;
s[las+1]=b[i].se;
}
else{
used[las]=1;
b[i].fi=las;
d[las]=i;
s[las]=b[i].se;
}
break;
}
if(trc!=i && j==0){
b[i].se = 1;
continue;
}
if(trc==i && j==0){
fori(k,las,las+(nn/(1<<j))){
if(k>=n)
break;
if(!used[k]){
sw[k]=0;
}
else{
sw[k]=s[k];
}
}
continue;
}
if(trc!=i && j!=0){
if(las+(nn/(1<<j)) <n)
las=las+(nn/(1<<j));
continue;
}
if(trc==i && j!=0){
fori(k,las,las+(nn/(1<<j))){
if(k>=n)
break;
if(!used[k]){
sw[k]=(b[i].se)%2;
}
else{
sw[k]=s[k];
}
}
continue;
}
}
}
/*fori(i,0,n){
s[i]=a[i].se;
d[i]=a[i].fi;
}*/
/*fori(i,0,80000){
tryCombination(sw);
}*/
answer(s,d);
return ;
}
