#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
vector<int> base={3, 3, 3, 3, 3, 2, 2, 1};
vector<vector<int>> v;
vector<vector<int>> states={{0}, {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}, {13, 14, 15}, {16, 17}, {18, 19}, {20}};
int n;
vector<int> divide(int depth, int l, int r){
int t=base[depth];
if (t==1) return {r};
if (t==2) return {(l+r)/2, r};
if (t==3) return {l+(r-l)/3, l+(r-l)/3*2, r};
}
void dnc(int depth, int l, int r, bool box){
if (l>r) return;
if (l==r){
v[states[depth][0]][0]=box;
for (int j=1; j<=n; ++j) if (j<l) v[states[depth][0]][j]=-1-box; else v[states[depth][0]][j]=-2+box;
return;
}
auto vv=divide(depth, l+1, r-1);
while (sz(vv)>1 && vv.back()<=vv[sz(vv)-2]) vv.pop_back();
for (int i=0; i<sz(states[depth]); ++i){
v[states[depth][i]][0]=box;
int id=0;
for (int j=1; j<=n; ++j){
if (j<=l) v[states[depth][i]][j]=-1-box;
else if (j>=r) v[states[depth][i]][j]=-2+box;
else{
if (j>vv[id]) ++id;
if (i<id) v[states[depth][i]][j]=-1-box;
else if (i>id) v[states[depth][i]][j]=-2+box;
else{
auto vvv=divide(depth+1, i?vv[i-1]:l+1, vv[i]);
while (sz(vvv)>1 && vvv.back()<=vvv[sz(vvv)-2]) vvv.pop_back();
int t=upper_bound(vvv.begin(), vvv.end(), j)-vvv.begin()-1;
t=max(t, 0);
v[states[depth][i]][j]=states[depth+1][t];
}
}
}
}
for (int i=0; i<sz(vv); ++i) dnc(depth+1, i?vv[i-1]:l+1, vv[i], box^1);
}
vector<vector<int>> devise_strategy(int N){
n=N;
vector<vector<int>>(21, vector<int>(n+1)).swap(v);
dnc(0, 1, n, 0);
return v;
}
