#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){
assert(ans[pos][0]==-1 or ans[pos][0]==ab);
ans[pos][0]=ab;
if(l==r) return;
ans[pos][l]=-1-(ab);
ans[pos][r]=-1-(!ab);
++l,--r;
if(l>r) return;
ll ch=dp[x-best[x]];
for(ll il=l, ir=min(r,l+ch-1), cnt=0;il<=r;il+=ch,ir+=min(r, ir+ch), ++cnt){
for(ll i=il;i<=ir;++i){
ans[pos][i]=nxt+cnt;
}
for(ll i=l-1;i<=r+1;++i){
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;
/*cout<< N<<endl;
for(auto v: ans){
for(auto u: v){
cout<< u <<" ";
}
cout<<endl;
}*/
return ans;
}
