#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;
{
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;
}
}
}
}
//~ int prev = (j - 1) % 3;
//~ a[j][0] = b&1;
//~ for(int i=1;i<=n;i++){
//~ int cur = get(i, b + 1);
//~ if(cur < prev){
//~ if(b&1) a[j][i] = -2;
//~ else a[j][i] = -1;
//~ }
//~ if(prev < cur){
//~ if(b&1) a[j][i] = -1;
//~ else a[j][i] = -2;
//~ }
//~ if(prev == cur){
//~ a[j][i] = a.size() + get(i, b);
//~ }
//~ }
}
a.push_back(b_);
a.push_back(b_);
a.push_back(b_);
}
for(int j=(int)a.size() - 3;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_);
//~ int third = (r_ - l_ + 3) / 3;
//~ rng[a.size()].push_back({l_ - 1, r_ + 1, l_, l_ + third - 1});
//~ for(int k=l_;k<l_ + third;k++){
//~ a[j][k] = a.size();
//~ }
//~ rng[a.size() + 1].push_back({l_ - 1, r_ + 1, l_ + third, l_ + 2 * third - 1});
//~ for(int k=l_+third;k<l_ + 2 * third;k++){
//~ a[j][k] = a.size() + 1;
//~ }
//~ rng[a.size() + 2].push_back({l_ - 1, r_ + 1, l_ + 2 * third, r_});
//~ for(int k=l_ + 2 * third;k<=r_;k++){
//~ a[j][k] = a.size() + 2;
//~ }
}
//~ int prev = (j - 1) % 3;
//~ a[j][0] = 0;
//~ for(int i=1;i<=n;i++){
//~ int cur = get(i, 1);
//~ if(cur < prev){
//~ a[j][i] = -1;
//~ }
//~ if(prev < cur){
//~ a[j][i] = -2;
//~ }
//~ if(prev == cur){
//~ int nxt = get(i, 0);
//~ if(nxt == 0){
//~ a[j][i] = -1;
//~ } if(nxt == 2){
//~ a[j][i] = -2;
//~ } if(nxt == 1){
//~ a[j][i] = a.size();
//~ }
//~ }
//~ }
}
//~ a.push_back(b_);
//~ a.back()[0] = 1;
//~ for(int i=1;i<=n;i++){
//~ int cur = get(i, 0);
//~ if(cur == 0){
//~ a.back()[i] = -2;
//~ } if(cur == 2){
//~ a.back()[i] = -1;
//~ }
//~ }
return a;
}
