#include "prison.h"
#include <vector>
#include <bits/stdc++.h>
int x = 21;
//int x = 5;
std::vector<std::vector<int>> ans;
int n;
void setans(int level, int idx, int val) {
if (idx >= 0 && idx < n) ans[level][idx+1] = val;
}
void dfs(int l, int r, int level) {
if (level % 2 == 0) // left side
for (int i = l - (r-l) - 1; i < l; i++) {
setans(level, i, -ans[level][0]-1);
}
if (level % 2 == 1) // right side
for (int i = r+1; i <= r + (r - l)+1; i++) {
setans(level, i, ans[level][0]-2);
}
for (int cur = level; cur <= x; cur++) {
setans(cur, l, -ans[cur][0]-1);
setans(cur, r, ans[cur][0]-2);
}
if (l+3 == r) {
for (int i = l+1; i < r; i++) {
setans(level, i, x);
}
setans(x, l+1, -ans[x][0]-1);
setans(x, r-1, ans[x][0]-2);
return;
}
int m = (l+r)/2;
for (int i = l+1; i < r; i++) {
setans(level, i, int((level+1)/2)*2 + 1 + (i > m));
}
dfs(l+1, m, int((level+1)/2)*2 +1);
dfs(m+1, r-1, int((level+1)/2)*2 + 2);
}
std::vector<std::vector<int>> devise_strategy(int N) {
n = N;
ans.assign(x+1, std::vector<int>(N+1, 0));
// side
for (int level = 0; level <= x; level++)
ans[level][0] = ((level+1)/2)%2;
dfs(0, 6141, 0);
// dfs(0, 21, 0);
/* for (auto a : ans) {
for (auto b : a) std::cout << (b < 0 ? " " : (b >= 10 ? " " : " ")) << b;
std::cout << "\n";
}*/
return ans;
}
