#include<bits/stdc++.h>
#include "prison.h"
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
vector<vector<int>>devise_strategy(int n){
vector<vector<int>>s;
function<void(int, int, int, int, int, int)>solve;
solve = [&] (int depth, int id, int l, int r, int L, int R){
if(l >= r){
return;
}
while(s.size() <= id){
s.emplace_back(vector<int>(n + 1, 0));
}
s[id][0] = depth & 1;
for(int i = l++; i >= L; i--){
s[id][i] = -s[id][0] - 1;
}
for(int i = r--; i <= R; i++){
s[id][i] = -(s[id][0] ^ 1) - 1;
}
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
for(int i = l; i <= r; i++){
if(i <= m1){
s[id][i] = depth * 3 + 1;
}
else if(i <= m2){
s[id][i] = depth * 3 + 2;
}
else{
s[id][i] = (depth + 1) * 3;
}
}
solve(depth + 1, depth * 3 + 1, l, m1, l - 1, r + 1);
solve(depth + 1, depth * 3 + 2, m1 + 1, m2, l - 1, r + 1);
solve(depth + 1, depth * 3 + 3, m2 + 1, r, l - 1, r + 1);
};
solve(0, 0, 1, n, 1, n);
for(int i = 0; i < s.size(); i++){
for(int j = 1; j <= n; j++){
minimize(s[i][j], int(s.size()) - 1);
}
}
return s;
}
