#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 base = 3, b = ceil_log(4999, base) - 1, x = base * (b + 1) - 2;
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;
if (b - b_bit == 0) {
assert(state == 0);
state++;
}
return mp(b - b_bit, state);
};
auto pack = [&](int bit, int state) {
int tmp = (b - bit) * base + state + 1;
if (bit == 0) {
assert(state == 1);
tmp--;
}
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);
if (bit - 1 == 0 && next_digit != 1) {
if (next_digit == 0) {
s[i][j] = (bit % 2 ? -1 : -2);
} else if (next_digit == 2) {
s[i][j] = (bit % 2 ? -2 : -1);
}
} else {
// 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;
}
