#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
int encode(pair<int, int> x){
return x.first*3+x.second+1;
}
pair<int, int> decode(int x){
return {(x-1)/3, (x-1)%3};
}
int p[]={1, 3, 9, 27, 81, 243, 729, 2187, 6561};
int getbit(int i, int j){
return j%p[8-i]/p[8-i-1];
}
vector<vector<int>> devise_strategy(int n){
vector<vector<int>> v(23, vector<int>(n+1));
for (int j=1; j<=n; ++j) v[0][j]=encode({0, getbit(0, j)});
for (int i=1; i<22; ++i){
auto p=decode(i);
v[i][0]=!(p.first&1ll);
for (int j=1; j<=n; ++j){
int t=getbit(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>18){
int t=getbit(p.first+1, j);
if (t==0) v[i][j]=-2;
if (t==2) v[i][j]=-1;
if (t==1) v[i][j]=22;
}
else v[i][j]=encode({p.first+1, getbit(p.first+1, j)});
}
}
}
v[22][0]=0;
for (int j=1; j<=n; ++j){
int t=getbit(7, j);
if (t==0) v[22][j]=-1;
else v[22][j]=-2;
}
return v;
}
