#include "prison.h"
#include <bits/stdc++.h>
#define ll int
#define vc vector
using namespace std;
#include <vector>
std::vector<std::vector<int>> devise_strategy(int N) {
vc<ll>dp(22);dp[0]=1;
vc<ll>best(22, -1);//todo best for 0 and 1
for(ll x=1;x<=21;++x){
for(ll j=1;x-j-1>=0;++j) if(dp[x]<2+j*dp[x-j])dp[x]=2+j*dp[x-j], best[x]=j;
}
vc<vc<ll>> ans(21, vc<ll>(N+1, -1));
function<void (ll, ll, ll, ll, ll, ll)> sim=[&](ll l, ll r, ll ab, ll x, ll pos, ll nxt){
//if(r-l+1>dp[x])cerr<<"x"<<x<<endl;
assert(pos<21);
ans[pos][0]=ab;
ans[pos][l]=-1-(ab);
ans[pos][r]=-1-(!ab);
++l,--r;
ll ch=dp[x-best[x]];
for(ll il=l, ir=min(r,il+ch-1), cnt=0;il<=r;il+=ch, ++cnt){
ir=min(r,il+ch-1);
//cerr<<l<<" "<<r<<" "<<il<<" "<<ir<<" " << ch<<endl;
assert(ir-il+1<=ch);
for(ll i=il;i<=ir;++i){
ans[pos][i]=nxt+cnt;
}
for(ll i=l-1;i<=r+1;++i){
assert(nxt+cnt<21);
if(i<il)ans[nxt+cnt][i]=-1-(!ab);
if(ir<i)ans[nxt+cnt][i]=-1-(ab);
}
sim(il, ir, !ab, x-best[x], nxt+cnt, nxt+best[x]);
}
};
sim(1, N, 0, 21, 0, 1);
for(ll i=0;i<21;++i)if(ans[i][0]==-1) ans[i][0]=0;
return ans;
}
