#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
const int B = 3;
vector<int> pw(1, 1);
while (pw.back() < N) pw.push_back(pw.back() * B);
int L = (int)pw.size() - 1;
int x = 1 + 2 * L * (B - 1);
vector<vector<int>> s(x + 1, vector<int>(N + 1, 0));
auto id = [&](int t, int d, int v) {
return 1 + 2 * t * (B - 1) + d * (B - 1) + (v - 1);
};
auto digit = [&](int a, int p) {
return (a / pw[p]) % B;
};
s[0][0] = 0;
for (int j = 1; j <= N; ++j) {
int d = digit(j - 1, L - 1);
if (d == 0) s[0][j] = -2;
else s[0][j] = id(L - 1, 0, d);
}
for (int t = L - 1; t >= 0; --t) {
for (int d = 0; d < 2; ++d) {
for (int v = 1; v < B; ++v) {
int cur = id(t, d, v);
s[cur][0] = d ^ 1;
for (int j = 1; j <= N; ++j) {
int w = digit(j - 1, t);
if (w < v) {
s[cur][j] = d ? -2 : -1;
} else if (w > v) {
s[cur][j] = d ? -1 : -2;
} else {
if (t == 0) {
s[cur][j] = d ? -1 : -2;
} else {
int nd = digit(j - 1, t - 1);
if (nd == 0) s[cur][j] = d ? -1 : -2;
else s[cur][j] = id(t - 1, d ^ 1, nd);
}
}
}
}
}
}
return s;
}
