#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int pot[15];
vector<vector<int>> devise_strategy(int N) {
vector<int> czesc (N+1,0);
vector<vector<int>> odp (23,czesc);
pot[0] = 1;
for (int x=1;x<13;x++) pot[x] = pot[x-1]*3;
odp[0][0] = 0;
for (int x=1;x<=N;x++) odp[0][x] = 1 + x/pot[7];
for (int y=1;y<7;y++){
odp[3*y-2][0] = y%2;
for (int x=1;x<=N;x++){
if ((x%pot[9-y])/pot[8-y] > 0) odp[3*y-2][x] = (y%2==0?-2:-1);
else odp[3*y-2][x] = 3*y + (x%pot[8-y])/pot[7-y] + 1;
}
odp[3*y-2][1] = (y%2==0?-1:-2); odp[3*y-2][N] = (y%2==0?-2:-1);
odp[3*y-1][0] = y%2;
for (int x=1;x<=N;x++){
if ((x%pot[9-y])/pot[8-y] > 1) odp[3*y-1][x] = (y%2==0?-2:-1);
else if ((x%pot[9-y])/pot[8-y] < 1) odp[3*y-1][x] = (y%2==0?-1:-2);
else odp[3*y-1][x] = 3*y + (x%pot[8-y])/pot[7-y] + 1;
}
odp[3*y-1][1] = (y%2==0?-1:-2); odp[3*y-1][N] = (y%2==0?-2:-1);
odp[3*y][0] = y%2;
for (int x=1;x<=N;x++){
if ((x%pot[9-y])/pot[8-y] < 2) odp[3*y][x] = (y%2==0?-1:-2);
else odp[3*y][x] = 3*y + (x%pot[8-y])/pot[7-y] + 1;
}
odp[3*y][1] = (y%2==0?-1:-2); odp[3*y][N] = (y%2==0?-2:-1);
}
odp[19][0] = 1;
for (int x=1;x<=N;x++){
if ((x%9)/3 > 0) odp[19][x] = -1;
else{
if (x%3==0) odp[19][x] = -2;
if (x%3==1) odp[19][x] = 22;
if (x%3==2) odp[19][x] = -1;
}
}
odp[19][1] = -2; odp[19][N] = -1;
odp[20][0] = 1;
for (int x=1;x<=N;x++){
if ((x%9)/3 > 1) odp[20][x] = -1;
else if ((x%9)/3 < 1) odp[20][x] = -2;
else{
if (x%3==0) odp[20][x] = -2;
if (x%3==1) odp[20][x] = 22;
if (x%3==2) odp[20][x] = -1;
}
}
odp[20][1] = -2; odp[20][N] = -1;
odp[21][0] = 1;
for (int x=1;x<=N;x++){
if ((x%9)/3 < 2) odp[21][x] = -2;
else{
if (x%3==0) odp[21][x] = -2;
if (x%3==1) odp[21][x] = 22;
if (x%3==2) odp[21][x] = -1;
}
}
odp[21][1] = -2; odp[21][N] = -1;
odp[22][0] = 0;
for (int x=1;x<=N;x++){
if (x%3==0) odp[22][x] = -1;
if (x%3==2) odp[22][x] = -2;
}
odp[22][1] = -1; odp[22][N] = -2;
/*for (int x=0;x<=24;x++){
for (int y=0;y<=N;y++) cout << odp[x][y] << ' ';
cout << '\n';
}*/
return odp;
}
