#ifdef __cplusplus
extern "C" {
#endif
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
#ifdef __cplusplus
}
#endif
#include <bits/stdc++.h>
using namespace std;
int ansS[5000], ansD[5000], guess[5000], NN;
void recur(int index, int L, int R, int x)
{
if (L==R)
{
int cnt=0;
for (int i=0; i<NN; i++)
{
if (ansS[i]==-1)
{
if (cnt==L)
{
ansS[i]=guess[i]=x;
ansD[i]=index;
return;
}
cnt++;
}
}
// cout << "-------------------------------------------\n";
}
// cout << "recur " << index << ' ' << L << ' ' << R << ' ' << x << '\n';
int mid=(L+R)/2, cnt=0;
for (int i=0; i<NN; i++)
{
// cout << "here\n";
if (ansS[i]==-1)
{
if (L<=cnt && cnt<=mid)
guess[i]=x;
else
guess[i]=1-x;
cnt++;
// cout << "guess " << i << " = " << guess[i] << '\n';
}
}
if (tryCombination(guess)==index)
recur(index, mid+1, R, x);
else
recur(index, L, mid, x);
}
void exploreCave(int N)
{
NN=N;
for (int i=0; i<N; i++)
ansS[i]=-1;
for (int i=0; i<N; i++)
{
for (int j=0; j<N; j++)
if (ansS[j]==-1)
guess[j]=0;
recur(i, 0, N-i-1, (tryCombination(guess)==i));
}
answer(ansS, ansD);
}
