#include "prison.h"
#include "bits/stdc++.h"
using namespace std;
const int M = 8;
int p[M];
int check(int x, int k) {
k--;
return ((x / p[k]) % 3);
}
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> ret(M * 3 + 1, vector<int>(N + 1));
ret[0][0] = 1;
p[0] = 1;
for (int i = 1; i < M; ++i) p[i] = p[i - 1] * 3;
for (int i = 1; i <= N; ++i) {
ret[0][i] = M + M * check(i, M);
}
for (int i = 1; i <= M * 3; ++i) {
int bit = i - ((i - 1) / M * M);
int state = (i - 1) / M;
if (bit % 2) {//we have the state of A
ret[i][0] = 1;
for (int j = 1; j <= N; ++j) {
if (state < check(j, bit)) {
ret[i][j] = -1;
} else if (state > check(j, bit)) {
ret[i][j] = -2;
} else {
if (bit > 1) {
ret[i][j] = bit - 1 + M * check(j, bit - 1);
}
}
}
} else {
ret[i][0] = 0;
for (int j = 1; j <= N; ++j) {
if (state < check(j, bit)) {
ret[i][j] = -2;
} else if (state > check(j, bit)) {
ret[i][j] = -1;
} else {
if (bit > 1) {
ret[i][j] = bit - 1 + M * check(j, bit - 1);
}
}
}
}
}
return ret;
}
