#include "cave.h"
#ifdef VANWIJ
#include"/home/user/code/bits/stdc++.h"
#define DBG 1
#else
#include"bits/stdc++.h"
#define DBG 0
#endif
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}
const int N = 5005;
int n;
int ansState[N], ansDoor[N];
int q[N];
int ask(){
int ret = tryCombination(q);
if(ret==-1) ret = n;
return ret;
}
bool can[N];
void exploreCave(int _n){
n = _n;
rep(i,0,n){
ansDoor[i] = -1;
}
// find switch that link to door
rep(door,0,n){
dbg(door);
// correct and wrong states
int correct, wrong;
rep(i,0,n){
can[i] = ansDoor[i]==-1;
if(can[i]){
q[i] = 1;
}
}
{
int ret = ask();
if(ret > door){
correct = 1; wrong = 0;
}
else{
correct = 0; wrong = 1;
}
}
while(1){
int cnt = 0;
rep(i,0,n){
cnt += can[i];
}
if(cnt==1) break;
bool flag = 0;
rep(i,0,n) if(can[i]){
if(flag) q[i] = correct;
else q[i] = wrong;
flag ^= 1;
}
int ret = ask();
if(ret > door){
rep(i,0,n) if(can[i]){
can[i] &= q[i]==correct;
}
}
else{
rep(i,0,n) if(can[i]){
can[i] &= q[i]==wrong;
}
}
}
int x = 0;
while(!can[x]) x++;
q[x] = correct;
ansState[x] = correct;
ansDoor[x] = door;
}
answer(ansState, ansDoor);
}
