#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
typedef long long ll;
void build(vector<vector<int>> &s, int idx, int bag, int l, int r)
{
s[idx][0] = bag;
s[idx][l] = - 2 + bag;
s[idx][r] = - 1 - bag;
if (l + 1 >= r)
return;
int m = (l + r) / 2;
for (int i = l; i <= m; i++)
{
if (i > l)
s[idx][i] = idx + 1 + (idx % 2);
s[idx + 2 + (idx % 2)][i] = - 1 + bag;
}
build(s, idx + 1 + (idx % 2), 1 - bag, l, m);
for (int i = m + 1; i <= r; i++)
{
if (i < r)
s[idx][i] = idx + 2 + (idx % 2);
s[idx + 1 + (idx % 2)][i] = - 2 + bag;
}
build(s, idx + 2 + (idx % 2), 1 - bag, m + 1, r);
}
vector<vector<int>> devise_strategy(int N)
{
vector<vector<int>> s(61, vector<int>(N+1));
build(s, 0, 0, 1, N);
bool found = false;
while (!found)
{
for (int x : s.back())
if (x != 0)
found = true;
if (!found)
s.pop_back();
}
return s;
}
