#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int pot[15];
vector<vector<int>> odp;
void zrob(int x, int l, int r, int nr){
if (r-l==1){
odp[x][l] = (odp[x][0]==0?-1:-2);
odp[x][r] = (odp[x][0]==0?-2:-1);
return;
}
if (r-l==2){
odp[x][l] = (odp[x][0]==0?-1:-2);
odp[x][l+1] = 3*nr+1;
odp[3*nr+1][0] = 1-odp[x][0];
odp[3*nr+1][l] = (odp[3*nr+1][0]==0?-1:-2); odp[3*nr+1][r] = (odp[3*nr+1][0]==0?-2:-1);
odp[x][r] = (odp[x][0]==0?-2:-1);
return;
}
if (l>r) 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+1;y<l + (r-l)/3;y++) odp[x][y] = 3*nr+1;
for (int y=l + (r-l)/3;y<=r;y++) odp[3*nr+1][y] = (odp[3*nr+1][0]==0?-2:-1);
odp[3*nr+1][l] = (odp[3*nr+2][0]==0?-1:-2);
zrob(3*nr+1,l+1,l + (r-l)/3-1,nr+1);
for (int y=l+(r-l)/3;y<l + 2*(r-l)/3;y++) odp[x][y] = 3*nr+2;
for (int y=l;y<l+(r-l)/3;y++) odp[3*nr+2][y] = (odp[3*nr+2][0]==0?-1:-2);
for (int y=l + 2*(r-l)/3;y<=r;y++) odp[3*nr+2][y] = (odp[3*nr+2][0]==0?-2:-1);
zrob(3*nr+2,l+(r-l)/3+1,l + 2*(r-l)/3-1,nr+1);
for (int y=l + 2*(r-l)/3;y<r;y++) odp[x][y] = 3*nr+3;
for (int y=l;y<l + 2*(r-l)/3;y++) odp[x][y] = (odp[3*nr+2][0]==0?-1:-2);
odp[3*nr+3][r] = (odp[3*nr+2][0]==0?-2:-1);
zrob(3*nr+3,l + 2*(r-l)/3+1,r-1,nr+1);
}
vector<vector<int>> devise_strategy(int N) {
vector<int> czesc (N+1,0);
vector<vector<int>> cos (23,czesc);
odp = cos;
zrob(0,1,N,0);
/*for (int x=0;x<23;x++){
for (int y=0;y<=N;y++){
cout << odp[x][y] << ' ';
}
cout << '\n';
}*/
return odp;
}
