#include "prison.h"
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int a[6] = {1667, 555, 185, 61, 20, 6};
int d[5050][10];
int f(int x, int t) {
if(d[x][t] != -1) return d[x][t];
if(t == 0) return d[x][t] = x;
int y = f(x, t-1);
if(y > 9998) return d[x][t] = y;
y %= a[t-1];
if(y == 0) return d[x][t] = 9999;
if(y == a[t-1]-1) return d[x][t] = 10000;
return d[x][t] = y-1;
}
std::vector<std::vector<int>> devise_strategy(int N) {
vector<vector<int> > v(21);
memset(d, -1, sizeof d);
v[0].resize(N+1);
v[0][0] = 0;
for(int j = 1; j <= N; j++) {
v[0][j] = j/a[0] + 1;
}
for(int i = 1; i < 19; i++) {
v[i].resize(N+1);
v[i][0] = (i+2)/3%2;
int q = (i-1)/3, r = (i-1)%3;
for(int j = 1; j <= N; j++) {
int x = f(j, q);
if(x == 9999) {
v[i][j] = -1-v[i][0];
continue;
}
else if(x == 10000) {
v[i][j] = v[i][0]-2;
continue;
}
int y = x / a[q], z = x % a[q];
if(r < y) v[i][j] = v[i][0]-2;
else if(r > y) v[i][j] = -1-v[i][0];
else {
if(z == 0) v[i][j] = -1-v[i][0];
else if(z == a[q]-1) v[i][j] = v[i][0]-2;
else {
if(q < 5) v[i][j] = (z-1)/a[q+1] + 1 + 3*(q+1);
else v[i][j] = 19 + (z > 2);
}
}
}
}
for(int i = 19; i < 21; i++) {
v[i].resize(N+1);
v[i][0] = 1;
int t = i-19;
for(int j = 1; j <= N; j++) {
int x = f(j, 6);
if(x == 9999) v[i][j] = -2;
else if(x == 10000) v[i][j] = -1;
else {
if(t < x/2) v[i][j] = -1;
else if(t > x/2) v[i][j] = -2;
else if(x % 2) v[i][j] = -1;
else v[i][j] = -2;
}
}
}
return v;
}
