#include "prison.h"
#include <vector>
#include <tuple>
#include <utility>
#include <map>
#include <cassert>
#include <deque>
using namespace std;
using ti = tuple<int, int, int, int>;
const int S[10] = {2, 2, 3, 3, 2, 3, 2, 2, 1};
const int O[10] = {1, 3, 5, 8, 11, 13, 16, 18, 20};
const int A_SMALL = -1;
const int B_SMALL = -2;
vector<vector<int>> devise_strategy(int N) {
deque<ti> V;
V.emplace_back(0, 0, 1, N);
vector<vector<int>> ans(21, vector<int>(N+1));
while (!V.empty()) {
auto [n, l, s, e] = V.front(); V.pop_front();
int me_small = (l & 1 ? B_SMALL : A_SMALL);
int me_big = (l & 1 ? A_SMALL : B_SMALL);
ans[n][0] = (l & 1);
ans[n][s] = me_small;
ans[n][e] = me_big;
if(e - s <= 1) continue;
int q = (e - s - 1) / S[l];
int r = (e - s - 1) % S[l];
int a = s + 1;
for(int i = 0; i < S[l]; i++) {
int b = a + (q + (i < r)) - 1;
int ch = O[l] + i;
V.emplace_back(ch, l+1, a, b);
for(int j = s; j < a; j++) ans[ch][j] = me_big;
for(int j = b + 1; j <= e; j++) ans[ch][j] = me_small;
for(int j = a; j <= b; j++) ans[n][j] = ch;
a = b + 1;
}
}
return ans;
}
