#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 20;
vector<vector<int>> devise_strategy(int N) {
vector<pair<int, int>> dp(M + 1);
dp[0] = make_pair(2, -1);
for (int i = 1; i <= M; i++) {
for (int j = 0; j < i; j++) {
dp[i] = max(dp[i], make_pair(dp[j].first * (i - j) + 2, i - j));
}
}
vector<int> split;
split.push_back(1);
int rem = M;
while (rem > 0) {
split.push_back(dp[rem].second);
rem -= dp[rem].second;
}
vector<vector<int>> repr(N + 1);
for (int i = 1; i <= N; i++) {
int pos = i - 1;
int len = dp[M].first;
int off = 1;
for (int j = 1; ; j++) {
if (pos == 0) {
repr[i].push_back(0);
break;
}
if (pos == len - 1) {
repr[i].push_back(M + 1);
break;
}
pos--;
len = (len - 2) / split[j];
repr[i].push_back(off + pos / len);
pos %= len;
off += split[j];
}
}
vector<vector<int>> res(M + 1, vector<int>(N + 1, 0));
int off = 0;
for (int i = 0; i < (int)split.size(); i++) {
for (int j = off; j < off + split[i]; j++) {
res[j][0] = (i & 1);
for (int k = 1; k <= N; k++) {
int prv = (i ? repr[k][i - 1] : 0);
if (prv != j) {
res[j][k] = (-1) - ((i & 1) ^ (prv > j));
continue;
}
int cur = repr[k][i];
if (cur == 0) {
res[j][k] = (-1) - (i & 1);
}
else if (cur == M + 1) {
res[j][k] = (-1) - ((i & 1) ^ 1);
}
else {
res[j][k] = cur;
}
}
}
off += split[i];
}
return res;
}
