#include<iostream>
#include<algorithm>
#include<vector>
#include "prison.h"
using namespace std;
int bitval(int bit,int num,int base)
{
vector<int>tobase;
while(num!=0)
{
tobase.push_back(num%base);
num/=base;
}
if(bit>=tobase.size())return 0;
return tobase[bit];
}
std::vector<std::vector<int>> devise_strategy(int N)
{
int n=N;
vector<vector<int>>s;
s.resize(23);
for(int i=0;i<=22;i++)s[i].resize(n+1);
s[0][0]=0;
for(int j=1;j<=n;j++)
{
s[0][j]=bitval(7,j,3)+1;
}
for(int i=1;i<=19;i+=3)
{
s[i][0]=(i+2)/3;
int bit=7-s[i][0];
s[i][0]=s[i][0]%2;
s[i+1][0]=s[i][0];
s[i+2][0]=s[i][0];
for(int j=1;j<=n;j++)
{
int valcheck=bitval(bit+1,j,3);
if(valcheck==2)
{
s[i][j]=(abs(bit)%2==0 ? -1 : -2);
s[i+1][j]=(abs(bit)%2==0 ? -1 : -2);
if(i==19)
{
if(bitval(bit,j,3)==2)s[i+2][j]=(abs(bit)%2==0 ? -1 : -2);
else if(bitval(bit,j,3)==0)s[i+2][j]=(abs(bit)%2==0 ? -2 : -1);
else
{
s[i+2][j]=22;
}
}
else s[i+2][j]=bitval(bit,j,3)+i+3;
}
else if(valcheck==1)
{
s[i][j]=(abs(bit)%2==0 ? -1 : -2);
if(i==19)
{
if(bitval(bit,j,3)==2)s[i+1][j]=(abs(bit)%2==0 ? -1 : -2);
else if(bitval(bit,j,3)==0)s[i+1][j]=(abs(bit)%2==0 ? -2 : -1);
else
{
s[i+1][j]=22;
}
}
else s[i+1][j]=bitval(bit,j,3)+i+3;
s[i+2][j]=(abs(bit)%2==0 ? -2 : -1);
}
else
{
if(i==19)
{
if(bitval(bit,j,3)==2)s[i][j]=(abs(bit)%2==0 ? -1 : -2);
else if(bitval(bit,j,3)==0)s[i][j]=(abs(bit)%2==0 ? -2 : -1);
else
{
s[i][j]=22;
}
}
else s[i][j]=bitval(bit,j,3)+i+3;
s[i+1][j]=(abs(bit)%2==0 ? -2 : -1);
s[i+2][j]=(abs(bit)%2==0 ? -2 : -1);
}
}
}
s[22][0]=0;
for(int j=1;j<=n;j++)
{
if(bitval(0,j,3)==0)s[22][j]=-1;
else if(bitval(0,j,3)==2)
{
s[22][j]=-2;
}
}
return s;
}
