#include <bits/stdc++.h>
#define ll long long
using namespace std;
int con(ll x) {
if (x == 1) return 2;
return 1;
}
vector<vector<int>> devise_strategy(int N) {
ll i, j, ab = 1, bit = 7, sig = 1, val, tam = 22, aBit, aVal;
// pot[k] = 3^k
vector<int> pot(9, 1);
for (i = 1; i <= bit; i++) pot[i] = pot[i - 1] * 3;
vector<vector<int>> ans(tam, vector<int>(N + 1, 0));
// definir qué bolsa mira cada estado
for (i = 1; i < tam; i += 3) {
for (j = 0; j < 3 && i + j < tam; j++)
ans[i + j][0] = ab;
ab = con(ab + 1) - 1;
}
// primer nivel
for (i = 1; i <= N; i++) {
val = (i / pot[bit]) % 3;
ans[0][i] = sig + val;
}
int aLevel = bit;
bit--;
sig += 3;
// construir niveles intermedios
for (j = 1; j < tam - 1; j++) {
for (i = 1; i <= N; i++) {
val = (i / pot[aLevel]) % 3;
aVal = (j - 1) % 3;
if (val < aVal) {
ans[j][i] = -(ans[j][0] + 1);
} else if (val > aVal) {
ans[j][i] = -con(ans[j][0] + 1);
} else {
val = (i / pot[bit]) % 3;
ans[j][i] = sig + val;
// pruning del último trío:
if (ans[j][i] == 22) { // este sería el estado "extra"
// en vez de ir a 22, ya decidimos directo:
if (val == 0)
ans[j][i] = -(ans[j][0] + 1); // A más chico
else if (val == 2)
ans[j][i] = -con(ans[j][0] + 1); // B más chico
else
ans[j][i] = 21; // único estado central
}
}
}
if (j % 3 == 0) {
aLevel = bit;
bit--;
sig += 3;
}
}
// último estado real = 21
for (i = 1; i <= N; i++) {
val = i % 3;
if (val == 0) ans[21][i] = -(ans[21][0] + 1);
else if (val == 2) ans[21][i] = -con(ans[21][0] + 1);
// si val == 1, en teoría no debería ocurrir que A == B,
// así que no hay transición válida ahí
}
return ans;
}
