#include "prison.h"
#include<iostream>
#include<cassert>
#include<algorithm>
#include<vector>
#include<array>
#include<utility>
#include<set>
#include<map>
#include<string>
#include<random>
using namespace std;
#define pii pair<int,int>
#define V vector
#define rep(i,a,b) for(int i=a; i<(int)b; i++)
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define nl '\n'
#define _ << " " <<
#define ff first
#define ss second
V<V<int>> g;
void dnc(int l,int r,int i,int who){
if(l > r) return;
g[i][0] = who;
int nxt = i;
while(nxt%3) nxt++;
V<pii> lr;
if(nxt==18){ // split two
int m = (l+r)/2;
if(l+1<=m) lr.push_back({l+1,m});
if(m+1<=r-1) lr.push_back({m+1,r-1});
}
else{ // split three
int m1 = (2*l+r)/3, m2 = (l+2*r)/3;
if(l+1<=m1) lr.push_back({l+1,m1});
if(m1+1<=m2) lr.push_back({m1+1,m2});
if(m2+1<=r-1) lr.push_back({m2+1,r-1});
}
for(int x=l; x<=r; x++){
if(x==l) g[i][x] = (who?-2:-1);
else if(x==r) g[i][x] = (who?-1:-2);
else{
rep(j,0,lr.size()) if(lr[j].ff<=x && x<=lr[j].ss){
g[i][x] = nxt+j+1;
}
}
}
rep(j,0,lr.size()){
auto[tl,tr] = lr[j];
for(int x=l; x<=tl-1; x++) g[nxt+j+1][x] = (who?-1:-2);
for(int x=tr+1; x<=r; x++) g[nxt+j+1][x] = (who?-2:-1);
dnc(tl,tr, nxt+j+1, who^1);
}
}
V<V<int>> devise_strategy(int N) {
g = V<V<int>>(21,V<int>(N+1));
dnc(1,N,0,0);
return g;
}
