#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
struct seg {
pair<int, int> old, cur;
};
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> vvi;
vector<vector<seg>> help;
help.push_back(vector<seg>());
vector<seg> vs;
seg tmp;
tmp.old = {1, N};
vvi.push_back(vector<int>(N + 1));
vvi[0][0] = 0;
for (int i = tmp.old.first; i >= 1; i--) vvi[0][i] = -1;
for (int i = tmp.old.second; i <= N; i++) vvi[0][i] = -2;
tmp.cur = {2, (N + 1) / 2};
for (int i = tmp.cur.first; i <= tmp.cur.second; i++) vvi[0][i] = 1;
vs.push_back(tmp);
help.push_back(vs);
vs.clear();
tmp.cur = {(N + 1) / 2 + 1, N - 1};
for (int i = tmp.cur.first; i <= tmp.cur.second; i++) vvi[0][i] = 2;
vs.push_back(tmp);
help.push_back(vs);
for (int i = 1; 1; i += 2) {
int curi = i;
for (int j=0;j<2;j++)
help.push_back(vector<seg>());
do {
vvi.push_back(vector<int>(N + 1));
if (curi % 4 == 1) vvi[i][0] = 1;
for (auto a : help[i]) {
for (int j = a.cur.first; j >= a.old.first; j--) {
if (curi % 4 == 1)
vvi[i][j] = -2;
else
vvi[i][j] = -1;
}
for (int j = a.cur.second; j <= a.old.second; j++) {
if (curi % 4 == 1)
vvi[i][j] = -1;
else
vvi[i][j] = -2;
}
seg tmp, tmp2;
tmp.old = a.cur;
tmp2.old = a.cur;
if ((tmp.old.second - tmp.old.first) % 2 == 1) {
tmp.cur = {tmp.old.first + 1, (tmp.old.first + tmp.old.second) / 2};
tmp2.cur = {(tmp.old.first + tmp.old.second) / 2 + 1,
tmp.old.second - 1};
} else {
tmp.cur = {tmp.old.first + 1, (tmp.old.first + tmp.old.second) / 2};
tmp2.cur = {(tmp.old.first + tmp.old.second) / 2 + 1,
tmp.old.second - 1};
if (curi % 4==1)
{
tmp.cur.second--;
tmp2.cur.first--;
}
}
help[curi + 2].push_back(tmp);
help[curi + 3].push_back(tmp2);
for (int j = tmp.cur.first;
j <= tmp.cur.second; j++)
vvi[i][j] = curi + 2;
for (int j = tmp2.cur.first;
j <= tmp2.cur.second; j++)
vvi[i][j] = curi + 3;
}
i++;
} while (i % 2 == 0);
i -= 2;
for (int j = 1; j <= N; j++)
if (vvi[i][j] > 0 || vvi[i + 1][j] > 0) goto A;
if(vvi.size()==23)
vvi.pop_back();
return vvi;
A:;
}
}
