#include "prison.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
const int B = 2;
int bag[30];
struct state
{
int l, r, a, b;
};
vector<state> spaces[30];
vector<vector<int>> devise_strategy(int N)
{
vector<vector<int>> sol;
bag[0] = 1;
spaces[0] = {state{1, N, 1, N}};
int x = 0;
for (int j = 0; j <= x; j++)
{
sol.emplace_back(vector<int>(N + 1, 0));
sol[j][0] = bag[j] - 1;
for (auto &[l, r, a, b] : spaces[j])
{
for (int k = l; k <= a; k++)
sol[j][k] = -bag[j];
for (int k = b; k <= r; k++)
sol[j][k] = -(bag[j] ^ 3);
l = a + 1, r = b - 1;
}
for (auto [l, r, a, b] : spaces[j])
{
if (r < l)
continue;
int hl = (l + l + r + 1) / 3, hr = (l + r + r + 2) / 3;
int p = (j + 2) / 3 * 3 + 1;
bag[p] = bag[p + 1] = bag[p + 2] = bag[j] ^ 3;
if (l == r)
{
sol[j][l] = p;
spaces[p].emplace_back(state{a, b, l, r});
x = max(x, p);
}
else if (l + 1 == r)
{
sol[j][l] = p;
spaces[p].emplace_back(state{a, b, l, l});
sol[j][r] = p + 1;
spaces[p + 1].emplace_back(state{a, b, r, r});
x = max(x, p + 1);
}
else
{
spaces[p].emplace_back(state{a, b, l, hl});
for (int k = l; k <= hl; k++)
sol[j][k] = p;
spaces[p + 1].emplace_back(state{a, b, hl + 1, hr});
for (int k = hl + 1; k <= hr; k++)
sol[j][k] = p + 1;
spaces[p + 2].emplace_back(state{a, b, hr + 1, r});
for (int k = hr + 1; k <= r; k++)
sol[j][k] = p + 2;
x = max(x, p + 2);
}
}
}
// for (int i = 0; i <= x; i++)
// {
// cout << sol[i][0] << " |";
// for (int j = 1; j <= N; j++)
// cout << ' ' << sol[i][j];
// cout << '\n';
// }
cerr << x << '\n';
return sol;
}
