#include<bits/stdc++.h>
#include "prison.h"
using namespace std;
vector<int> gr[200000];
int spint[200000][2];
void fill_int(int le, int ri)
{
int id=2;
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;
if(ri-le<=5)
{
int mid=(le+ri)/2;
gr[i].push_back(id);
spint[id][0]=le+1;
spint[id][1]=mid;
id++;
gr[i].push_back(id);
spint[id][0]=mid+1;
spint[id][1]=ri-1;
id++;
}
else
{
int m1=(2*le+ri)/3, m2=(le+2*ri)/3;
gr[i].push_back(id);
spint[id][0]=le+1;
spint[id][1]=m1;
id++;
gr[i].push_back(id);
spint[id][0]=m1+1;
spint[id][1]=m2;
id++;
gr[i].push_back(id);
spint[id][0]=m2+1;
spint[id][1]=ri-1;
id++;
}
//cout<<i<<" "<<le<<" "<<ri<<endl;
}
}
vector<vector<int> > ans;
vector<vector<int> > devise_strategy(int N)
{
fill_int(1, N);
ans.resize(21);
for(int i=0; i<=20; i++)
{
int brp=(i+2)/3;
if(brp%2==0)
{
//cout<<"A: ";
ans[i].push_back(0);
for(int brA=1; brA<=N; brA++)
{
//cout<<brA<<" ";
bool fl=1;
int pos=1;
for(int j=0; j<brp-1; j++)
{
if(gr[pos].size()<2) {fl=0; break;}
if(spint[gr[pos][0]][0]<=brA && brA<=spint[gr[pos][0]][1]) pos=gr[pos][0];
else if(spint[gr[pos][1]][0]<=brA && brA<=spint[gr[pos][1]][1]) pos=gr[pos][1];
else pos=gr[pos][2];
}
if(!fl)
{
ans[i].push_back(0);
continue;
}
if(i%3==1)
{
if(gr[pos].size()<1) {ans[i].push_back(0); continue;}
if(i) pos=gr[pos][0];
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[gr[pos][0]][1]) ans[i].push_back(i+3);
else if(brA<=spint[gr[pos][1]][1]) ans[i].push_back(i+4);
else ans[i].push_back(i+5);
}
else if(i%3==2)
{
if(gr[pos].size()<2) {ans[i].push_back(0); continue;}
if(i) pos=gr[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[gr[pos][0]][1]) ans[i].push_back(i+2);
else if(brA<=spint[gr[pos][1]][1]) ans[i].push_back(i+3);
else ans[i].push_back(i+4);
}
else
{
if(gr[pos].size()<3) {ans[i].push_back(0); continue;}
if(i) pos=gr[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[gr[pos][0]][1]) ans[i].push_back(i+1);
else if(brA<=spint[gr[pos][1]][1]) ans[i].push_back(i+2);
else ans[i].push_back(i+3);
}
}
//cout<<endl;
}
else
{
//cout<<"B: ";
ans[i].push_back(1);
for(int brB=1; brB<=N; brB++)
{
//cout<<brB<<" ";
bool fl=1;
int pos=1;
for(int j=0; j<brp-1; j++)
{
if(gr[pos].size()<2) {fl=0; break;}
if(spint[gr[pos][0]][0]<=brB && brB<=spint[gr[pos][0]][1]) pos=gr[pos][0];
else if(spint[gr[pos][1]][0]<=brB && brB<=spint[gr[pos][1]][1]) pos=gr[pos][1];
else pos=gr[pos][2];
}
if(!fl)
{
ans[i].push_back(0);
continue;
}
if(i%3==1)
{
if(gr[pos].size()<1) {ans[i].push_back(0); continue;}
if(i) pos=gr[pos][0];
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[gr[pos][0]][1]) ans[i].push_back(i+3);
else if(brB<=spint[gr[pos][1]][1]) ans[i].push_back(i+4);
else ans[i].push_back(i+5);
}
else if(i%3==2)
{
if(gr[pos].size()<2) {ans[i].push_back(0); continue;}
if(i) pos=gr[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[gr[pos][0]][1]) ans[i].push_back(i+2);
else if(brB<=spint[gr[pos][1]][1]) ans[i].push_back(i+3);
else ans[i].push_back(i+4);
}
else
{
if(gr[pos].size()<3) {ans[i].push_back(0); continue;}
if(i) pos=gr[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[gr[pos][0]][1]) ans[i].push_back(i+1);
else if(brB<=spint[gr[pos][1]][1]) ans[i].push_back(i+2);
else ans[i].push_back(i+3);
}
}
//cout<<endl;
}
}
return ans;
}
