#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 (nr<6){
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-1,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});
}
else{
odp[7+2*nr][0] = 1-odp[x][0]; odp[7+2*nr+1][0] = 1-odp[x][0];
for (int y=l;y<l+(r-l+1)/2 && y<=n;y++) odp[x][y] = 7+2*nr;
zrob(7+2*nr,l,l+(r-l+1)/2-1,nr+1,{l-1,r+1});
for (int y=l+(r-l+1)/2;y<=r && y<=n;y++) odp[x][y] = 7+2*nr+1;
zrob(7+2*nr+1,l+(r-l+1)/2,r,nr+1,{l-1,r+1});
}
}
vector<vector<int>> devise_strategy(int N) {
vector<int> czesc (N+1,0);
vector<vector<int>> cos (21,czesc);
odp = cos;
n = N;
odp[0][0] = 0;
zrob(0,1,5102,0,{1,5102});
/*for (int x=0;x<21;x++){
for (int y=0;y<=N;y++){
cout << odp[x][y] << ' ';
}
cout << '\n';
}*/
return odp;
}
