#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
vector<vector<int>> ans;
void calc(int prev, int level, int where, int prev_l, int prev_r, int L, int R, int iter){
int idx = (level-1)*3+where;
if (iter%2 == 0) ans[idx][0] = 1;
for (int i=L; i<=R; ++i) ans[prev][i] = idx;
for (int i=prev_l; i<=L; ++i) ans[idx][i] = -ans[idx][0]-1;
for (int i=R; i<=prev_r; ++i) ans[idx][i] = ans[idx][0]-2;
L++; R--;
if (L > R) return;
if (R-L == 0){
calc(idx,level+1,1,L-1,R+1,L,R,iter+1);
return;
}
if (R-L <= 3){
calc(idx,level+1,1,L-1,R+1,L,L+(R-L)/2,iter+1);
calc(idx,level+1,2,L-1,R+1,R-(R-L)/2,R,iter+1);
return;
}
int op = 1;
if (0 <= (R-L)/3){
calc(idx,level+1,op,L-1,R+1,L,L+(R-L)/3,iter+1);
++op;
}
if (L+(R-L)/3+1 <= R-(R-L)/3-1){
calc(idx,level+1,op,L-1,R+1,L+(R-L)/3+1,R-(R-L)/3-1,iter+1);
++op;
}
if (0 <= (R-L)/3 and R-(R-L)/3 > L+(R-L)/3){
calc(idx,level+1,op,L-1,R+1,R-(R-L)/3,R,iter+1);
++op;
}
}
vector<vector<int>> devise_strategy(int n){
for (int i=0; i<21; ++i){
ans.emplace_back(vector<int>(n+1));
}
calc(0,0,3,1,n,1,n,0);
return ans;
}
