#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
int encode(pair<int, int> x){
if (x.first<4) return x.first*2+x.second+1;
return (x.first-1)*3+x.second;
}
pair<int, int> decode(int x){
if (x<9) return {(x-1)/2, (x-1)%2};
return {x/3+1, x%3};
}
int p[]={1, 3, 9, 27, 81, 243, 729, 2187, 6561};
int getbit3(int i, int j){
i-=2;
return j%p[8-i]/p[8-i-1];
}
int getbit2(int i, int j){
return (j>>(12ll-i))&1ll;
}
vector<vector<int>> devise_strategy(int n){
vector<vector<int>> v(21, vector<int>(n+1));
for (int j=1; j<=n; ++j) v[0][j]=encode({0, getbit2(0, j)});
for (int i=1; i<18; ++i){
auto p=decode(i);
v[i][0]=!(p.first&1ll);
for (int j=1; j<=n; ++j){
int t=(i<9)?getbit2(p.first, j):getbit3(p.first, j);
if (p.second<t) v[i][j]=v[i][0]-2;
else if (p.second>t) v[i][j]=(!v[i][0])-2;
else{
if (i>14){
int r=j%9;
if (r==0) v[i][j]=-2;
else if (r==8) v[i][j]=-1;
else if (r<=4) v[i][j]=18;
else v[i][j]=19;
}
else v[i][j]=encode({p.first+1, (p.first+1<4)?getbit2(p.first+1, j):getbit3(p.first+1, j)});
}
}
}
for (int i=18; i<20; ++i){
for (int j=1; j<=n; ++j){
int t=j%9;
if (j==9) v[i][j]=-2;
else if (t==0) v[i][j]=-1;
else if (t==8) v[i][j]=-2;
else if (i==18){
if (t==1) v[i][j]=-1;
else if (t>=4) v[i][j]=-2;
else v[i][j]=20;
}else{
if (t<=5) v[i][j]=-1;
else if (t==7) v[i][j]=-2;
else v[i][j]=20;
}
}
}
v[20][0]=1;
for (int j=1; j<=n; ++j){
int r=j%9;
if (j==9) v[20][j]=-1;
else if (r<=4){
if (r<=2) v[20][j]=-2;
else v[20][j]=-1;
}else{
if (r<=6) v[20][j]=-2;
else v[20][j]=-1;
}
}
return v;
}
