#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
typedef vector<int> vi;
typedef pair<int,int> ii;
int n,dp[25],best[25];
vector<int> split,start;
vector<vi> s;
void dnc(int num,int stage,int tosee,int l,int r){
//pf("dnc: %d %d %d %d %d\n",num,stage,tosee,l,r);
if(n<l||r<n)return;
int sz=(r-l-1)/split[stage];
vector<ii> rng;
for(int i=0;i<split[stage];++i){
rng.pb({l+1+i*sz,l+(i+1)*sz});
}
if(num==0){
s[num][0]=0;//identify A
for(int i=l;i<=r;++i){
if(n<i)break;
if(i==l)s[num][i]=-1;//A smaller
else if(i==r)s[num][i]=-2;//B smaller
else{
for(int j=0;j<split[stage];++j){
auto[nl,nr]=rng[j];
if(nl<=i&&i<=nr){
s[num][i]=start[stage]+j;
dnc(start[stage]+j,0,1,l,r);
}
}
}
}
}
else{
if(tosee==0)s[num][0]=0;//identify A
else s[num][0]=1;//identify B
for(int i=l;i<=r;++i){
if(n<i)break;
if(i==l)s[num][i]=(tosee==0)?-1:-2;//if we see A, A smaller else B smaller
else if(i==r)s[num][i]=(tosee==0)?-2:-1;//if we see A, B smaller else A smaller
else{
int pv=num-start[stage];
for(int j=0;j<split[stage];++j){
auto[nl,nr]=rng[j];
if(nl<=i&&i<=nr){
if(pv<j)s[num][i]=(tosee==0)?-2:-1;//if we see A, then B smaller else A smaller
else if(j<pv)s[num][i]=(tosee==0)?-1:-2;//if we see A, then A smaller else B smaller
else{
if(i==nl)s[num][i]=(tosee==0)?-1:-2;//if we see A, then A smaller else B smaller
else if(i==nr)s[num][i]=(tosee==0)?-2:-1;//if we see A, then B smaller else A smaller
else{
vector<ii> nrng;
int sz2=(nr-nl-1)/split[stage+1];
for(int k=0;k<split[stage+1];++k){
int nnl=nl+1+k*sz2,nnr=nl+(k+1)*sz2;
if(nnl<=i&&i<=nnr){
s[num][i]=start[stage+1]+k;
dnc(start[stage+1]+k,stage+1,1-tosee,nl,nr);
}
}
}
}
}
}
}
}
}
}
vector<vi> devise_strategy(int N){
n=N;
dp[0]=2;
for(int i=1;i<=20;++i){
for(int k=1;k<=i;++k){
if(dp[i-k]*k+2>dp[i]){
dp[i]=dp[i-k]*k+2;
best[i]=k;
}
}
}
int cur=20;
start.pb(1);
while(cur){
split.pb(best[cur]);
start.pb(start.back()+best[cur]);
cur-=best[cur];
}
//for(int i:split)pf("%d ",i);pf("\n");
//for(int i:start)pf("%d ",i);pf("\n");
s.resize(21);
for(int i=0;i<=20;++i){
s[i].resize(n+1);
}
dnc(0,0,0,1,dp[20]);
//for(int i=0;i<=20;++i){
//pf("%d: ",i);
//for(int x:s[i])pf("%d ",x);
//pf("\n");
//}
return s;
}
