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