#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> ans;
int n;
set<array<int,4>> se;
void DnC(int x,int a,int l,int r)
{
if (se.count({x,a,l,r})) return;
se.insert({x,a,l,r});
ans[x][0]=a;
int l1=l+1,r1=r-1;
for (int i=1;i<=n;i++)
if (i<=l)
ans[x][i]=-1-a;
else if(i>=r)
ans[x][i]=-2+a;
else
{
if (r1-l1+1>=3)
{
int len=r1-l1+1;
int e=l1+len/3+(len%3>0),e1=e+len/3+(len%3>1);
if (i<e)
ans[x][i]=(x+2)/3+1,DnC(ans[x][i],1-a,l1,e-1);
else if(i<e1)
ans[x][i]=(x+2)/3+2,DnC(ans[x][i],1-a,e,e1-1);
else
ans[x][i]=(x+2)/3+3,DnC(ans[x][i],1-a,e1,r1);
}
else
{
if (i==l1)
ans[x][i]=(x+2)/3+1,DnC(ans[x][i],1-a,l1,l1);
else
ans[x][i]=(x+2)/3+2,DnC(ans[x][i],1-a,r1,r1);
}
}
}
vector<vector<int>> devise_strategy(int N)
{
n=N;
ans=vector<vector<int>>(21,vector<int>(n+1));
DnC(0,0,1,n);
return ans;
}
