#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> s, idx;
vector<int> k = {3, 3, 3, 3, 3, 2, 2, 1}, v = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 7}, w = {1, 4, 7, 10, 13, 16, 18, 20};
void doidx(int l, int r, int d){
if (d > 7) return;
int step = (r-l-1)/k[d];
idx[l][d] = -1;
idx[r][d] = -2;
for (int j=0; j<k[d]; j++){
for (int i=0; i<step; i++) idx[l+1+j*step+i][d] = j;
doidx(l+1+j*step, l+1+(j+1)*step-1, d+1);
}
}
vector<vector<int>> devise_strategy(int N){
s.resize(21, vector<int>(N+1, 0));
idx.resize(5589, vector<int>(8, 0));
doidx(1, 5588, 0);
s[0][0] = 0;
s[0][1] = -1;
for (int i=2; i<=N; i++) s[0][i] = idx[i][0]+1;
for (int i=1; i<=20; i++){
int d = v[i-1], val = i-w[d];
s[i][0] = (d+1)%2;
for (int j=1; j<=N; j++){
if (idx[j][d] == -1) s[i][j] = -(s[i][0]+1);
else if (idx[j][d] == -2) s[i][j] = s[i][0]-2;
else if (idx[j][d] < val) s[i][j] = -(s[i][0]+1);
else if (idx[j][d] > val) s[i][j] = s[i][0]-2;
else if (d != 7){
if (idx[j][d+1] == -1) s[i][j] = -(s[i][0]+1);
else if (idx[j][d+1] == -2) s[i][j] = s[i][0]-2;
else s[i][j] = w[d+1]+idx[j][d+1];
}
}
}
return s;
}
