#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<vector<int>> odp;
int n;
void zrob(int x, int l, int r, int nr, pair<int,int> poprz){
if (l>n) return;
for (int y=poprz.first;y<=l && y<=n;y++) odp[x][y] = (odp[x][0]==0?-1:-2);
for (int y=r;y<=poprz.second && y<=n;y++) odp[x][y] = (odp[x][0]==0?-2:-1);
l++; r--;
if (l>r) return;
if (l==r){
odp[3*nr+1][0] = 1-odp[x][0];
odp[x][l] = 3*nr+1;
odp[3*nr+1][l-1] = (odp[3*nr+1][0]==0?-1:-2);
if (r+1 <= n) odp[3*nr+1][r+1] = (odp[3*nr+1][0]==0?-2:-1);
return;
}
odp[3*nr+1][0] = 1-odp[x][0]; odp[3*nr+2][0] = 1-odp[x][0]; odp[3*nr+3][0] = 1-odp[x][0];
for (int y=l;y<l+(r-l+1)/3 && y<=n;y++) odp[x][y] = 3*nr+1;
zrob(3*nr+1,l,l+(r-l+1)/3 - 1,nr+1,{l-1,r+1});
for (int y=l+(r-l+1)/3;y<l+2*(r-l+1)/3 && y<=n;y++) odp[x][y] = 3*nr+2;
zrob(3*nr+2,l+(r-l+1)/3,l+2*(r-l+1)/3,nr+1,{l-1,r+1});
for (int y=l+2*(r-l+1)/3;y<=r && y<=n;y++) odp[x][y] = 3*nr+3;
zrob(3*nr+3,l+2*(r-l+1)/3,r,nr+1,{l-1,r+1});
}
vector<vector<int>> devise_strategy(int N) {
vector<int> czesc (N+1,0);
vector<vector<int>> cos (24,czesc);
odp = cos;
n = N;
odp[0][0] = 0;
zrob(0,1,6560,0,{1,6560});
/*for (int x=0;x<21;x++){
for (int y=0;y<=N;y++){
cout << odp[x][y] << ' ';
}
cout << '\n';
}*/
return odp;
}
