#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int dvd[7] = {3, 3, 3, 3, 3, 3, 2};
int cdiv(int a, int b){
return (a + b - 1) / b;
}
tuple<int, int, int> split(int l, int r, int v, int did){
if (v == l || v == r) return {-1, -1, -1};
l++; r--;
int gsz = cdiv(r - l + 1, dvd[did]), 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, i);
if (gid == -1) break;
}
return {l, r, gid};
}
vector<vector<int>> devise_strategy(int N){
vector<vector<int>> ret(21, vector<int>(N + 1, 0));
ret[0][0] = 0;
for (int v = 1; v <= N; v++){
if (v == 1) ret[0][v] = -1;
else if (v == 5000) ret[0][v] = -2;
else ret[0][v] = 1 + get<2>(split(1, 5000, v, 0));
}
for (int i = 1; i < 21; 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 == -1) continue;
else if (gid < mod) ret[i][v] = -(ret[i][0] + 1);
else if (gid > mod) ret[i][v] = -(2 - ret[i][0]);
else if (v == l) ret[i][v] = -(ret[i][0] + 1);
else if (v == r) ret[i][v] = -(2 - ret[i][0]);
else if (dv < 8) ret[i][v] = dv * 3 + 1 + get<2>(split(l, r, v, dv));
}
}
return ret;
}
