#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int n) {
const int M = 20, N = 5102;
int xl = 0, xr = 1;
vector strat(M + 1, vector<int>(N));
vector<int> mapping(N), div = {3, 3, 3, 3, 3, 3, 2, 0};
for (int k = 0; k < (int) div.size(); ++k) {
for (int l = 0, r = 0; l < N; l = r) {
while (r < N && mapping[r] == mapping[l]) ++r;
for (int x = xl; x < xr; ++x) {
if (mapping[l] < x) {
fill(strat[x].begin() + l, strat[x].begin() + r, -1);
} else if (mapping[l] > x) {
fill(strat[x].begin() + l, strat[x].begin() + r, INT_MAX);
} else {
strat[x][l] = -1, strat[x][r - 1] = INT_MAX;
for (int i = l + 1; i < r - 1; ++i) {
strat[x][i] = xr + div[k] * (i - l - 1) / (r - l - 2);
}
}
}
}
for (int i = 0; i < N; ++i) {
if (xl <= mapping[i] && mapping[i] < xr) {
mapping[i] = strat[mapping[i]][i];
}
}
for (int x = xl; x < xr; ++x) {
strat[x].resize(n);
for (auto &y : strat[x]) if (y == INT_MAX) y = -2;
strat[x].insert(strat[x].begin(), k % 2);
if (k % 2) for (auto &y : strat[x]) if (y < 0) y = -3 - y;
}
xl = xr, xr += div[k];
}
return strat;
}
