#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int p3[8];
int cdiv(int a, int b){
return (a + b - 1) / b;
}
tuple<int, int, int> split(int l, int r, int v){
int gsz = cdiv(r - l + 1, 3), gid = (v - l) / gsz;
l = l + gsz * gid;
r = min(r, l + gsz - 1);
return {l, r, gid};
}
tuple<int, int, int> getr(int dv, int v){
int l = 1, r = 5000, gid = -1;
for (int i = 0; i < dv; i++) tie(l, r, gid) = split(l, r, v);
return {l, r, gid};
}
vector<vector<int>> devise_strategy(int N){
vector<vector<int>> ret(25, vector<int>(N + 1, 0));
ret[0][0] = 0;
for (int v = 1; v <= N; v++) ret[0][v] = 1 + get<2>(split(1, 5000, v));
for (int i = 1; i < 25; i++){
int dv = (i + 2) / 3, mod = (i + 2) % 3;
ret[i][0] = dv & 1;
for (int v = 1; v <= N; v++){
int l, r, gid; tie(l, r, gid) = getr(dv, v);
if (gid < mod) ret[i][v] = -(ret[i][0] + 1);
else if (gid > mod) ret[i][v] = -(2 - ret[i][0]);
else if (dv < 8) ret[i][v] = dv * 3 + 1 + get<2>(split(l, r, v));
}
}
return ret;
}
