#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int x, int dep, int whi, int l1, int r1, int l, int r, vector<vector<int> >& ans){
int cur = dep * 3 + whi;
for(int i = l; i <= r; i++) ans[x][i] = cur;
for(int i = l1; i <= l; i++){
if(ans[cur][0] == 0) ans[cur][i] = -1;
else ans[cur][i] = -2;
}
for(int i = r; i <= r1; i++){
if(ans[cur][0] == 0) ans[cur][i] = -2;
else ans[cur][i] = -1;
}
l++; r--;
if(l > r) return;
if (r - l < 2) {
solve(cur, dep + 1, 1, l - 1, r + 1, l, r, ans);
return;
}
if (r - l < 4) {
int mid = (l + r) / 2;
solve(cur, dep + 1, 1, l - 1, r + 1, l, mid, ans);
solve(cur, dep + 1, 2, l - 1, r + 1, mid + 1, r, ans);
return;
}
int len = (r - l) / 3;
solve(cur, dep + 1, 1, l - 1, r + 1, l, l + len, ans);
solve(cur, dep + 1, 2, l - 1, r + 1, l + len + 1, r - len, ans);
solve(cur, dep + 1, 3, l - 1, r + 1, r - len + 1, r, ans);
}
vector<vector<int>> devise_strategy(int n) {
vector<vector<int> > ans(22, vector<int> (n + 1, 0));
for(int i = 0; i <= 20; i++){
if((i + 2) % 6 < 3) ans[i][0] = 1;
}
solve(0, -1, 3, 1, n, 1, n, ans);
return ans;
}
