#include "bits/stdc++.h"
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FR(i,l,r) for(int i=(l);i>=(r);--i)
typedef long long ll;
const int maxn=1000005;
const int mod=1e9+7;
const int mox=2000*500+505;
const int inf=1e9;
vector<vector<int> > s;
int dp[22];
void build(int idx,int l,int r,int pl,int pr,int bag){
s[idx][0]=bag;
F(v,pl,l)s[idx][v]=(bag==0)?-1:-2;//smaller
F(v,r+1,pr+1)s[idx][v]=(bag==0)?-2:-1;//larger
s[idx][l]=(bag==0)?-1:-2;
s[idx][r]=(bag==0)?-2:-1;
int inl=l+1,inr=r-1;
if(inl>inr)return;
int len=inr-inl+1;
bool ternary;
int capbin=(idx+2<=20)?dp[idx+2]:0,mxbin=2+2*capbin;
int capter=(idx+3<=20)?dp[idx+3]:0,mxter=2+3*capter;
if(len<=(inr-inl+1) && mxbin>=len)ternary=0;
else ternary=1;
if(mxter>mxbin)ternary=(mxbin<len);
else ternary=0;
if(ternary){
int split=len/3,r1=inl+split-1;
int r2=r1+split;
if(len%3==2){
r1++;
r2++;
}else if(len%3==1)r1++;
int cid[3]={idx+1,idx+2,idx+3};
int bounds[4]={inl,r1,r2,inr};
F(k,0,3){
int cl=bounds[k]+(k==0?0:1);
int cr=bounds[k+1];
F(v,cl,cr+1)s[idx][v]=cid[k];
build(cid[k],cl,cr,inl,inr,1-bag);
}
}else{
int split=(len>>1),mid=inl+split-1;
int cid[2]={idx+1,idx+2};
int bounds[3]={inl,mid,inr};
F(k,0,2){
int cl=bounds[k]+(k==0?0:1);
int cr=bounds[k+1];
F(v,cl,cr+1)s[idx][v]=cid[k];
build(cid[k],cl,cr,inl,inr,1-bag);
}
}
}
vector<vector<int> > devise_strategy(int N){
s.assign(23,vector<int>(N+1,0));
FR(i,20,0){
int val=0;
if(i+2<=21)val=2*dp[i+2]+2;
int val2=0;
if(i+3<=21)val2=3*dp[i+3]+2;
dp[i]=max(val,val2);
}
build(0,1,N,1,N,0);
s.resize(21);
return s;
}
