#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
ll X = 20;
vector<vector<int>> ans; int N;
int itype[9][5103]; //x -> type (1, 2, 3 or -1 (TOP) or -2 (BOTTOM))
void wtype(ll a, ll b, ll d) {
if (a>=b) {
return;
}
assert(d<9);
ll len = b-a+1;
if (len>=188) {
itype[d][a]=-2;
itype[d][b]=-1;
ll nwid = len/3;
for (ll i=(a+1);i<=(a+3*nwid);i++) {
itype[d][i]=(i-a-1)/nwid;
}
wtype(a+1,a+nwid,d+1);
wtype(a+nwid+1,a+2*nwid,d+1);
wtype(a+2*nwid+1,a+3*nwid,d+1);
} else {
itype[d][a]=-2;
itype[d][b]=-1;
ll nwid = (len-2)/2;
for (ll i=(a+1);i<=(a+2*nwid);i++) {
itype[d][i]=(i-a-1)/nwid;
}
wtype(a+1,a+nwid,d+1);
wtype(a+nwid+1,b-1,d+1);
}
}
void prc(ll v) {
for (ll i=1;i<=N;i++) {
ll inp;
ll ncur;
ll nxt;
if (v<=12) {
inp = (v-1)%3;
ncur = (v-1)/3;
nxt = 3*ncur+4;
} else {
inp = (v-1)%2;
ncur = (v-1)/2-2;
nxt = 2*ncur+7;
}
ll rd = itype[ncur][i];
if (rd<0) {
if ((ans[v][0]==0)^(rd==-1)) {
//checking A XOR isMax
//min if checking A
ans[v][i]=-1;
} else {
ans[v][i]=-2;
}
} else {
if (rd>inp) {
if (ans[v][0]==0) {
//this is higher than other + checking A
ans[v][i]=-2;
} else {
ans[v][i]=-1;
}
} else if (rd<inp) {
if (ans[v][0]==0) {
//this is lower than other + checking A
ans[v][i]=-1;
} else {
ans[v][i]=-2;
}
} else {
//ans[v][i]=itype[ncur+1][i]+nxt;
if (itype[ncur+1][i]<0) {
if ((ans[v][0]==0)^(itype[ncur+1][i]==-1)) {
//checking A XOR isMax
//min if checking A
ans[v][i]=-1;
} else {
ans[v][i]=-2;
}
} else {
if (v<=18) {
ans[v][i]=itype[ncur+1][i]+nxt;
}
}
}
}
}
}
vector<vector<int>> devise_strategy(int _N) {
N = _N;
vector<int> TEMP(N+1,0);
for (ll i=0;i<=20;i++) {
ans.push_back(TEMP);
}
wtype(1,5102,0); //write type
ans[0][0]=0;
ans[0][1]=-1;
for (ll i=2;i<=N;i++) {
ans[0][i]=itype[0][i]+1;
}
ans[1][0]=1; //wtype 1
ans[2][0]=1;
ans[3][0]=1;
ans[4][0]=0; //2
ans[5][0]=0;
ans[6][0]=0;
ans[7][0]=1; //3
ans[8][0]=1;
ans[9][0]=1;
ans[10][0]=0; //4
ans[11][0]=0;
ans[12][0]=0;
ans[13][0]=1; //5
ans[14][0]=1;
ans[15][1]=0; //6
ans[16][1]=0;
ans[17][0]=1; //7
ans[18][0]=1;
ans[19][1]=0; //8
ans[20][1]=0;
for (ll i=1;i<=20;i++) {
prc(i);
}
return ans;
//output -1 = A is lower
}
