#include<bits/stdc++.h>
#include "prison.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,dp[5009],dp2[5009],FX[5009];
vector <vector <int> > f;
map <vector <int>, bool> mp;
void rec(int q, int w, int rr, int l, int r, bool bo, int cnt, int dep){
int i,j;
vector <int> V;
V.push_back(q);V.push_back(w);V.push_back(rr);V.push_back(l);V.push_back(r);V.push_back(bo);V.push_back(cnt);
if(mp[V]==1) return;
mp[V]=1;
f[rr][0]=bo;
//
for(i=l; i<=r; i++){
if(i<q){
//esaa patara(bo)
if(bo==0) f[rr][i]=-1; else f[rr][i]=-2;
continue;
}
if(i>w){
//isaa patara
if(bo==0) f[rr][i]=-2; else f[rr][i]=-1;
continue;
}
if(i==q){
//esaa patara
if(bo==0) f[rr][i]=-1; else f[rr][i]=-2;
continue;
}
if(i==w){
//isaa patara
if(bo==0) f[rr][i]=-2; else f[rr][i]=-1;
continue;
}
pair <int, int> p[5];int pi=0;
int len=w-q+1;
if(FX[dep]==0){
FX[dep]=dp2[len];
}
int qw=(len-2)/FX[dep],we=(len-2)%FX[dep];
p[0].second=q;
for(j=1; j<=FX[dep]; j++){
pi++;
p[j].first=p[j-1].second+1;p[j].second=p[j].first+qw-1;
if(j<=we) p[j].second++;
p[j].second=min(p[j].second,w-1);
}
for(j=1; j<=pi; j++){
if(p[j].first<=i&&i<=p[j].second){
f[rr][i]=cnt+j;
rec(p[j].first,p[j].second,cnt+j,q,w,!bo,cnt+pi,dep+1);
break;
}
}
}
}
vector<vector<int> > devise_strategy(int N) {
a=N;
dp[0]=0;dp[1]=dp[2]=0;
for(i=3; i<=a; i++){
dp[i]=i;
for(j=2; j<=3; j++){
c=(i-2)/j;
if((i-2)%j!=0) c++;
if(dp[i]>dp[c]+j){
dp[i]=dp[c]+j;dp2[i]=j;
}
}
}
int X=dp[a]+1;
f.resize(X);
for(i=0; i<X; i++){
f[i].resize(a+1);
}
rec(1,a,0,1,a,0,0,1);
return f;
}
