#include<bits/stdc++.h>
using namespace std;
//#include "prison.h"
typedef int ll;
vector<vector<ll>> s;
ll cad[]={ 3, 3, 3, 3, 3, 2, 2, 1, 2};
ll P[24][5588]={ };
void sol(ll p,ll a, ll b)
{
if(a>=b) return;
P[p][a]=-1e9;
P[p][b]=1e9;
if(a+1==b) return;
ll t1=(b-a-1)/cad[p];
ll t2=(b-a-1)%cad[p];
ll c=0;
for(int i=a+1; i<b;c++)
{
for(int j=0;j<t1+t2; j++)
{
P[p][i+j]=c;
}
sol(p+1,i,i+t1+t2-1);
i=i+t1+t2;
t2--;t2=max(t2,0);
}
}
ll Hash(ll p, ll vp) { return vp*8+p; }
std::vector<std::vector<int>> devise_strategy(int n) {
sol(0,1,5588);
s.assign(24,vector<ll>(n+1,0));
s[0][0]=0;s[0][1]=-1;s[0][n]=-2;
for(int i=2; i<n; i++)
s[0][i]=Hash(0,P[0][i])+1;
for(int i=1; i<24; i++)
{
ll temp=i-1;
ll va=temp%8;
temp/=8;
swap(va,temp);
s[i][0]=max(((temp+1)%2),0);
for(int j=1; j<=n; j++)
{
ll vp=P[temp][j];
if(va==vp)s[i][j]=Hash(temp+1,P[temp+1][j])+1;
else if((s[i][0]==0&&vp<va)||(s[i][0]==1&&vp>va)) s[i][j]=-1;
else s[i][j]=-2;
if(va==vp&&P[temp+1][j]>=24) s[i][j]=-2+s[i][0];
else if(va==vp&&P[temp+1][j]<-1e7) s[i][j]=-1-s[i][0];
}
}
/*for(int i=1; i<24; i++)
{
cout<<s[i][0]<<" ";
ll temp=i-1;
ll va=temp%8;
temp/=8;
swap(va,temp);
cout<<temp<<va<<P[temp][210]<<" ";
//for(int j=1; j<=4; j++)
{
cout<<s[i][4]<<P[(i-1)%8][4]<<" "<<s[i][210]<<P[(i-1)%8][210]<<" ";;
}
cout<<"\n";
}*/
return s;
}
