#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
vector<int> pow3(1, 1);
while (pow3.back() < N) pow3.push_back(pow3.back() * 3);
int L = (int)pow3.size() - 1;
int S = 1 + 3 * L;
vector<vector<int>> ans(S, vector<int>(N + 1, 0));
auto state = [&](int pos, int dig) {
return 1 + pos * 3 + dig;
};
for (int j = 1; j <= N; ++j) {
int d = (j / pow3[L - 1]) % 3;
ans[0][j] = state(0, d);
}
for (int pos = 0; pos < L; ++pos) {
int p = L - 1 - pos;
for (int da = 0; da < 3; ++da) {
int id = state(pos, da);
ans[id][0] = 1;
for (int b = 1; b <= N; ++b) {
int db = (b / pow3[p]) % 3;
if (db < da) {
ans[id][b] = -2;
} else if (db > da) {
ans[id][b] = -1;
} else if (pos == L - 1) {
ans[id][b] = -1;
} else {
int nd = (b / pow3[p - 1]) % 3;
ans[id][b] = state(pos + 1, nd);
}
}
}
}
return ans;
}
