#include "prison.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll
vector<vector<ii>> devise_strategy(ii n) {
vector<vector<ii>> a(1, vector<ii>(n + 1));
vector<vector<ar<int, 4>>> rng(100);
a[0][0] = 1;
int l = 1, r = n;
a[0][l] = -2, a[0][r] = -1;
l++, r--;
int third = (r - l + 3) / 3;
rng[a.size()].push_back({l - 1, r + 1, l, l + third - 1});
for(int i=l;i<l+third;i++){
a[0][i] = a.size();
}
rng[a.size() + 1].push_back({l - 1, r + 1, l + third, l + 2 * third - 1});
for(int i=l+third;i<l+2*third;i++){
a[0][i] = a.size() + 1;
}
rng[a.size() + 2].push_back({l - 1, r + 1, l + 2 * third, r});
for(int i=l+2*third;i<=r;i++){
a[0][i] = a.size() + 2;
}
vector<int> b_(n + 1, 0);
a.push_back(b_);
a.push_back(b_);
a.push_back(b_);
for(int b=6;b>0;b--){
for(int j=(int)a.size() - 3;j<(int)a.size();j++){
a[j][0] = b & 1;
for(auto [l, r, l_, r_] : rng[j]){
for(int k=l;k<=l_;k++){
if(a[j][0]){
a[j][k] = -2;
} else {
a[j][k] = -1;
}
}
for(int k=r_;k<=r;k++){
if(a[j][0]){
a[j][k] = -1;
} else {
a[j][k] = -2;
}
}
l_++, r_--;
int third = (r_ - l_ + 3) / 3;
if(b == 1) third = 2;
{
int _l = l_, _r = min(r_, l_ + third - 1);
if(_l <= _r){
rng[a.size()].push_back({l_ - 1, r_ + 1, _l, _r});
for(int k=_l;k<=_r;k++){
a[j][k] = a.size();
}
}
}
{
int _l = l_ + third, _r = min(r_, l_ + 2 * third - 1);
if(_l <= _r){
rng[a.size() + 1].push_back({l_ - 1, r_ + 1, _l, _r});
for(int k=_l;k<=_r;k++){
a[j][k] = a.size() + 1;
}
}
}
{
int _l = l_ + 2 * third, _r = r_;
if(_l <= _r){
rng[a.size() + 2].push_back({l_ - 1, r_ + 1, _l, _r});
for(int k=_l;k<=_r;k++){
a[j][k] = a.size() + 2;
}
}
}
}
}
a.push_back(b_);
a.push_back(b_);
a.push_back(b_);
}
//~ cout<<rng[a.size() - 1][0][0]<<" ";
//~ cout<<rng[a.size() - 1][0][1]<<" ";
//~ cout<<rng[a.size() - 1][0][2]<<" ";
//~ cout<<rng[a.size() - 1][0][3]<<endl;
assert(rng[a.size() - 1].empty());
a.pop_back();
for(int j=(int)a.size() - 2;j<(int)a.size();j++){
a[j][0] = 0;
for(auto [l, r, l_, r_] : rng[j]){
for(int k=l;k<=l_;k++){
a[j][k] = -1;
}
for(int k=r_;k<=r;k++){
a[j][k] = -2;
}
l_++, r_--;
assert(l_ > r_);
}
}
return a;
}
