#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
template<typename T>
int len(T &a){
return a.size();
}
#define a -1
#define b -2
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<std::vector<int>> devise_strategy(int n) {
vector<vector<int>> res;
auto construct = [&](auto &construct, int step, int i, int box, int al, int ar, int bl, int br)->void{
//cout << i << ' ' << box << ' ' << al << ' ' << ar << ' ' << bl << ' ' << br << endl;
if(box == 0){
if(bl > br) return;
while(len(res) <= i) res.push_back(vector<int>(n + 1));
//cout << len(res) << endl;
res[i][0] = 0;
//cout << al << ' ' << ar << endl;
for(int j = al; j <= bl; j ++){
res[i][j] = a;
}
for(int j = br; j <= ar; j ++){
res[i][j] = b;
}
al = bl + 1;
ar = br - 1;
if(al > ar) return;
if(ar - al == 1){
for(int j = al; j <= ar; j ++) res[i][j] = step * 2 - 1;
construct(construct, step + 1, step * 2 - 1, box ^ 1, al, ar, bl, br);
return;
}
int mid = (al + ar) / 2;
for(int j = al; j <= mid; j ++) res[i][j] = step * 2 - 1;
for(int j = mid + 1; j <= ar; j ++) res[i][j] = step * 2;
construct(construct, step + 1, step * 2 - 1, box ^ 1, al, mid, bl, br);
construct(construct, step + 1, step * 2, box ^ 1, mid + 1, ar, bl, br);
}else{
if(al > ar) return;
while(len(res) <= i) res.push_back(vector<int>(n + 1));
res[i][0] = 1;
for(int j = bl; j <= al; j ++){
res[i][j] = b;
}
for(int j = ar; j <= br; j ++){
res[i][j] = a;
}
bl = al + 1;
br = ar - 1;
if(bl > br) return;
if(br - bl == 1){
for(int j = bl; j <= br; j ++) res[i][j] = step * 2 - 1;
construct(construct, step + 1, step * 2 - 1, box ^ 1, al, ar, bl, br);
return;
}
int mid = (bl + br) / 2;
for(int j = bl; j <= mid; j ++){
res[i][j] = step * 2 - 1;
}
for(int j = mid + 1; j <= br; j ++){
res[i][j] = step * 2;
}
construct(construct, step + 1, step * 2 - 1, box ^ 1, al, ar, bl, mid);
construct(construct, step + 1, step * 2, box ^ 1, al, ar, mid + 1, br);
}
};
construct(construct, 1, 0, 0, 1, n, 1, n);
return res;
}
