#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
const int X[9] = { 3, 3, 3, 3, 3, 2, 2, 1 };
const int Y[9] = { 0, 1, 4, 7, 10, 13, 16, 18, 20 };
int a[10][5050];
void init(int l, int r, int k) {
a[k][l] = -1;
a[k][r] = -2;
if (r - l <= 1) return;
++l; --r;
int d = (r - l + X[k]) / X[k];
int c = 0;
for (; l + d - 1 <= r; l += d) {
for (int j = l; j < l + d; j++) {
a[k][j] = c;
}
++c;
init(l, l + d - 1, k + 1);
}
if (l <= r) {
for (int j = l; j <= r; j++) {
a[k][j] = c;
}
++c;
init(l, r, k + 1);
}
}
vector<vector<int>> devise_strategy(int n) {
init(1, 5000, 0);
vector<vector<int>> ans(21, vector<int>(n + 1));
for (int i = 0; i < 21; i++) {
int m = 0;
for (int j = 8; j >= 0; j--) {
if (i >= Y[j]) {
m = j; break;
}
}
ans[i][0] = m & 1;
for (int j = 1; j <= n; j++) {
if (m != 0) {
if (a[m - 1][j] == -1) {
ans[i][j] = -1 - ans[i][0];
continue;
}
if (a[m - 1][j] == -2) {
ans[i][j] = -2 + ans[i][0];
continue;
}
if (i - Y[m] != a[m - 1][j]) {
if (i - Y[m] < a[m - 1][j]) ans[i][j] = -2 + ans[i][0];
else ans[i][j] = -1 - ans[i][0];
continue;
}
}
if (a[m][j] == -1) ans[i][j] = -1 - ans[i][0];
else if (a[m][j] == -2) ans[i][j] = -2 + ans[i][0];
else if (i < 20) {
ans[i][j] = Y[m + 1] + a[m][j];
}
}
}
return ans;
}
