#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
using ii = pair<int, int>;
vector<vector<int> > devise_strategy(int N) {
auto ceil_log = [&](int n, int k) {
int ret = 0, tmp = 1;
while (tmp < n) {
tmp *= k;
ret++;
}
return ret;
};
int min_sf = (int)1e9, base = -1, b = -1;
for (int i = 2; i <= N; i++) {
int j = ceil_log(N - 1, i);
if (min_sf > i * (j + 1)) {
min_sf = i * (j + 1);
base = i;
b = j;
}
}
int x = min_sf;
vector<vector<int> > s(x + 1, vector<int>(N + 1));
auto unpack = [&](int v) {
if (v == 0) {
return mp(b, -1);
}
v--;
int b_bit = v / base, state = v % base;
return mp(b - b_bit, state);
};
auto pack = [&](int bit, int state) {
int tmp = (b - bit) * base + state + 1;
assert(0 <= tmp && tmp <= x);
return tmp;
};
auto get_digit = [&](int num, int pos) {
while (pos--) {
num /= base;
}
return num % base;
};
for (int i = 0; i <= x; i++) {
auto [bit, state] = unpack(i);
if (state == -1) {
s[i][0] = bit % 2;
for (int j = 1; j <= N; j++) {
// find digit at position bit of j
int digit = get_digit(j - 1, bit);
assert(0 <= digit && digit < base);
// write (bit, digit)
s[i][j] = pack(bit, digit);
}
} else {
s[i][0] = !(bit % 2);
for (int j = 1; j <= N; j++) {
// find digit at position bit of j
int digit = get_digit(j - 1, bit);
if (digit == state) {
if (bit == 0) {
s[i][j] = 0;
} else {
int next_digit = get_digit(j - 1, bit - 1);
// write (bit - 1, next_digit)
s[i][j] = pack(bit - 1, next_digit);
}
} else if (digit > state) {
s[i][j] = (bit % 2 ? -2 : -1);
} else {
s[i][j] = (bit % 2 ? -1 : -2);
}
}
}
}
return s;
}
