#include "cave.h"
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
// warning: ld is rougly 2x slower than double. Proof: ld: https://oj.uz/submission/319677 double: https://oj.uz/submission/319678
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define endl '\n'
#define test int testc;cin>>testc;while(testc--)
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
int* get(vi& t)
{
int* a = &t[0];
return a;
}
int n;
vi ans, state;
void solve(int i)
{
vi t(n, -1);
int type = 0;
F0R(j, n)
{
if (ans[j] != -1)t[j] = state[j];
}
F0R(j, n)if (t[j] == -1)t[j] = type;
int result = tryCombination(get(t));
assert(result == -1 || result >= i);
if (result != -1 && result <= i)type = 1;
int l = 0, r = n - 1;
while (l < r)
{
int m = (l + r) / 2;
F0R(j, n)
{
if (ans[j] != -1)t[j] = state[j];
else
{
if (j <= m)t[j] = type; else t[j] = 1 - type;
}
}
result = tryCombination(get(t));
assert(result == -1 || result >= i);
if (result == -1 || result > i)r = m;
else l = m + 1;
}
ans[l] = i;
state[l] = type;
}
void exploreCave(int temporary)
{
n = temporary;
ans.rsz(n, -1);
state.rsz(n, -1);
F0R(i, n)
{
solve(i);
}
answer(get(state), get(ans));
}
