#include "prison.h"
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
int m;
vector<int> dp, opt;
vector<vector<int>> s;
void rek(int written, int lst_possible_written, int x, int lo, int hi, int lo1, int hi1, int bag) {
s[written][0] = bag;
for(int i = lo1;i <= lo;i++) s[written][i] = bag ? -2 : -1;
for(int i = hi;i <= hi1;i++) s[written][i] = bag ? -1 : -2;
if(x == 0) return;
int l = lo + 1, r = hi - 1;
int gap = dp[x - opt[x]], cnt = 1;
for(int i = l;i < r;i += gap) {
for(int j = i;j < i + gap;j++)
s[written][j] = lst_possible_written + cnt;
rek(lst_possible_written + cnt, lst_possible_written + opt[x], x - opt[x], i, i + gap - 1, lo, hi, !bag);
cnt++;
}
}
vector<vector<int>> devise_strategy(int N) {
dp.pb(2), opt.pb(1);
while(dp.back() < N) {
int x = (int)dp.size();
dp.pb(0), opt.pb(0);
for(int i = 1;i <= x;i++) {
if(i * dp[x - i] + 2 > dp[x])
dp[x] = i * dp[x - i] + 2, opt[x] = i;
}
}
m = (int)dp.size();
vector<int> v(dp.back() + 1, 0);
for(int i = 0;i < m;i++) s.pb(v);
rek(0, 0, m - 1, 1, dp.back(), 1, dp.back(), 0);
for(int i = 0;i < m;i++) {
for(int j : s[i]) cout << j << " ";
cout << "\n";
while((int)s[i].size() > N + 1) s[i].pop_back();
}
return s;
}
