#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll nxt(ll w, ll x){
if(w==0){
ll a=x;
if(a==1) return -1;
else{
ll ans;
for(ll i=1; i<=12; i++){
if((a&(1ll<<i))>0) ans=i;
}
return ans;
}
}
else if(w<=12){
ll b=x;
ll ans=-1;
for(ll i=0; i<=12; i++){
if((b&(1ll<<i))>0) ans=i;
}
ll b1=-1, l=-1;
for(ll i=0; i<=12; i++){
if((b&(1ll<<i))>0) b1=l;
else l=i;
}
if(ans==-1) return -1;
else if(ans==w) return 19+((b1&(1ll<<3))>0);
else if(ans<w) return -2;
else return -1;
}
else if(w>=15){
ll bit=(w-13)/2, y=(w-13)%2;
if(bit%2==1){
ll a=-1, l=-1;
for(ll i=0; i<=12; i++){
if((x&(1ll<<i))>0) a=l;
else l=i;
}
ll la=(a&(1ll<<bit)), lb=y;
if(la>lb) return -2;
else if(lb>la) return -1;
else return 13+(bit-1)*2+(a&(1ll<<(bit-1))>0);
}
else{
ll b=-1, l=-1;
for(ll i=0; i<=12; i++){
if((x&(1ll<<i))>0) b=l;
else l=i;
}
ll lb=(b&(1ll<<bit)), la=y;
if(la>lb) return -2;
else if(lb>la) return -1;
else return 13+(bit-1)*2+(b&(1ll<<(bit-1))>0);
}
}
else{
ll bit=0, y=(w-13)%2;
ll b=-1, l=-1;
for(ll i=0; i<=12; i++){
if((x&(1ll<<i))>0) b=l;
else l=i;
}
ll lb=b%2, la=y;
if(la>lb) return -2;
else return -1;
}
}
vector<vector<int>> devise_strategy(int n) {
vector<vector<int>> ans(21,vector<int>(n+1,0));
ans[0][0]=0;
for(ll i=1; i<=12; i++) ans[i][0]=1;
ans[13][0]=1;
ans[14][0]=1;
ans[15][0]=0;
ans[16][0]=0;
ans[17][0]=1;
ans[18][0]=1;
ans[19][0]=0;
ans[20][0]=0;
for(ll w=0; w<=20; w++){
for(ll x=1; x<=n; x++){
ans[w][x]=nxt(w,x);
// cout<<ans[w][x]<<" ";
}
// cout<<endl;
}
return ans;
}
