#include<bits/stdc++.h>
#include "prison.h"
using namespace std;
int spint[200000][2];
void fill_int(int le, int ri)
{
spint[1][0]=le;
spint[1][1]=ri;
for(int i=1; i<20000; i++)
{
le=spint[i][0];
ri=spint[i][1];
if(ri-le<=1) continue;
spint[2*i][0]=le+1;
spint[2*i][1]=(le+ri)/2;
spint[2*i+1][0]=(le+ri)/2+1;
spint[2*i+1][1]=ri-1;
}
}
vector<vector<int> > ans;
vector<vector<int> > devise_strategy(int N)
{
fill_int(1, N);
ans.resize(22);
for(int i=0; i<=21; i++)
{
///cout<<i<<endl;
int brp=(i+1)/2;
if(brp%2==0)
{
ans[i].push_back(0);
for(int brA=1; brA<=N; brA++)
{
int pos=1;
for(int j=0; j<brp-1; j++)
{
if(spint[2*pos][0]<=brA && brA<=spint[2*pos][1]) pos*=2;
else pos=pos*2+1;
}
if(i%2)
{
if(i) pos*=2;
if(brA<=spint[pos][0]) ans[i].push_back(-1);
else if(brA>=spint[pos][1]) ans[i].push_back(-2);
else if(brA<=(spint[pos][0]+spint[pos][1])/2) ans[i].push_back(i+2);
else ans[i].push_back(i+3);
}
else
{
if(i) pos=2*pos+1;
if(brA<=spint[pos][0]) ans[i].push_back(-1);
else if(brA>=spint[pos][1]) ans[i].push_back(-2);
else if(brA<=(spint[pos][0]+spint[pos][1])/2) ans[i].push_back(i+1);
else ans[i].push_back(i+2);
}
}
}
else
{
ans[i].push_back(1);
for(int brB=1; brB<=N; brB++)
{
int pos=1;
for(int j=0; j<brp-1; j++)
{
if(spint[2*pos][0]<=brB && brB<=spint[2*pos][1]) pos*=2;
else pos=pos*2+1;
}
if(i%2)
{
pos*=2;
if(brB<=spint[pos][0]) ans[i].push_back(-2);
else if(brB>=spint[pos][1]) ans[i].push_back(-1);
else if(brB<=(spint[pos][0]+spint[pos][1])/2) ans[i].push_back(i+2);
else ans[i].push_back(i+3);
}
else
{
pos=2*pos+1;
if(brB<=spint[pos][0]) ans[i].push_back(-2);
else if(brB>=spint[pos][1]) ans[i].push_back(-1);
else if(brB<=(spint[pos][0]+spint[pos][1])/2) ans[i].push_back(i+1);
else ans[i].push_back(i+2);
}
}
}
}
return ans;
}
