#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
vector<int> radix;
int prod = 1;
while (prod < N) {
radix.push_back(3);
prod *= 3;
}
int levels = (int)radix.size();
vector<int> place(levels);
place[levels - 1] = 1;
for (int i = levels - 2; i >= 0; --i) {
place[i] = place[i + 1] * radix[i + 1];
}
vector<int> offset(levels + 1, 1);
for (int i = 0; i < levels; ++i) {
offset[i + 1] = offset[i] + radix[i];
}
int x = offset[levels] - 1;
vector<vector<int>> s(x + 1, vector<int>(N + 1, 0));
auto digit = [&](int v, int level) {
return (v / place[level]) % radix[level];
};
s[0][0] = 0;
for (int j = 1; j <= N; ++j) {
s[0][j] = offset[0] + digit(j - 1, 0);
}
for (int level = 0; level < levels; ++level) {
for (int remembered = 0; remembered < radix[level]; ++remembered) {
int state = offset[level] + remembered;
int inspect = (level + 1) & 1;
s[state][0] = inspect;
for (int j = 1; j <= N; ++j) {
int d = digit(j - 1, level);
if (d < remembered) {
s[state][j] = inspect == 1 ? -2 : -1;
} else if (d > remembered) {
s[state][j] = inspect == 1 ? -1 : -2;
} else if (level + 1 == levels) {
s[state][j] = inspect == 1 ? -1 : -2;
} else {
s[state][j] = offset[level + 1] + digit(j - 1, level + 1);
}
}
}
}
return s;
}
