#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
const long long mm=9,dva[mm]={1,3,3,3,3,3,3,2,0};
long long peu[mm],od[5069],pc[mm][5069],z=0;
void dnc(long long cdh,long long lb,long long rb)
{
long long i;
for(i=cdh;i<mm;i++)
{
pc[i][lb]=-1;
pc[i][rb]=-2;
}
lb++;
rb--;
if(lb<=rb)
{
long long j,md[dva[cdh]+1];
for(i=0;i<=dva[cdh];i++)
{
md[i]=lb-1+(rb-lb+1)*i/dva[cdh];
}
for(i=0;i<dva[cdh];i++)
{
for(j=md[i]+1;j<=md[i+1];j++)
{
pc[cdh][j]=i;
}
dnc(cdh+1,md[i]+1,md[i+1]);
}
}
}
vector<vector<int>> devise_strategy(int n)
{
long long i,j,k,w,e;
vector<vector<int>> cvv;
for(i=0;i<mm;i++)
{
peu[i]=z;
for(j=0;j<dva[i];j++)
{
od[z]=i;
z++;
}
}
z--;
dnc(1,1,n);
for(i=0;i<=z;i++)
{
vector<int> cv;
k=od[i];
e=k%2;
cv.push_back(e);
for(j=1;j<=n;j++)
{
w=pc[k][j];
if(w<0)
{
cv.push_back(w^e);
}
else if(w<i)
{
cv.push_back(-1^e);
}
else if(w>i)
{
cv.push_back(-2^e);
}
else
{
w=pc[k+1][j];
if(w<0)
{
cv.push_back(w^e);
}
else
{
cv.push_back(w);
}
}
}
cvv.push_back(cv);
}
return cvv;
}
