#include "prison.h"
#include <vector>
using namespace std;
constexpr int M[] = {2, 6, 20, 62, 188, 566, 1700, 5102};
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> ans(21, vector<int>(M[7] + 1));
ans[0][0] = 0;
ans[0][1] = -1;
ans[0][M[7]] = -2;
for(int i = 2; i < M[7]; i++) ans[0][i] = 1 + (i - 2) / M[6];
vector<int> chk(M[7] + 1);
chk[1] = chk[M[7]] = 1;
for(int t = 1, u = 6; t <= 16; t += 3, u--) {
ans[t][0] = ans[t + 1][0] = ans[t + 2][0] = !ans[t - 1][0];
for(int i = 1, j; ; i = j) {
while(i < M[7] && chk[i]) i++;
if(i == M[7]) break;
for(j = i + 1; !chk[j]; j++);
ans[t][i - 1] = ans[t + 1][i - 1] = ans[t + 2][i - 1] = -1 - ans[t][0];
ans[t][j] = ans[t + 1][j] = ans[t + 2][j] = -2 + ans[t][0];
for(int x = 0; x < 3; x++) {
int S = i + x * M[u];
int E = S + M[u];
chk[S] = chk[E - 1] = 1;
for(int y = 0; y < 3; y++) {
if(x != y) fill(ans[t + y].begin() + S, ans[t + y].begin() + E, -1 - ((x > y) ^ ans[t][0]));
else {
ans[t + y][S] = -1 - ans[t][0];
ans[t + y][E - 1] = -2 + ans[t][0];
for(int z = S + 1; z < E - 1; z++) ans[t + y][z] = t + 3 + (z - S - 1) / M[u - 1];
}
}
}
}
}
ans[19][0] = ans[20][0] = !ans[18][0];
for(int i = 1, j; ; i = j) {
while(i < M[7] && chk[i]) i++;
if(i == M[7]) break;
for(j = i + 1; !chk[j]; j++);
for(int k = i - 1; k <= j; k++) {
ans[19][k] = -1 - (k <= i);
ans[20][k] = -1 - (k < j - 1);
}
}
for(int i = 0; i <= 20; i++) ans[i].resize(N + 1);
return ans;
}
