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