#include "bits/stdc++.h"
using namespace std;
int p3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};
// base 3
int get_bit(int n, int bit) {
return (n % p3[bit + 1]) / p3[bit];
}
const int NBIT = 8;
std::pair<int,int> decode(int encoded) {
return {
NBIT - encoded / 4 - 1,
encoded % 4,
};
}
int encode(int bit, int t) {
if (bit < 0) return 0;
return (NBIT - bit - 1) * 4 + t;
}
std::vector<std::vector<int>> devise_strategy(int n) {
const int NSTATE = NBIT * 4;
std::vector<std::vector<int>> res(NSTATE, std::vector<int> (n+1, 0));
for (int state = 0; state < NSTATE; ++state) {
auto [bit, t] = decode(state);
if (t == 0) res[state][0] = 0;
else res[state][0] = 1;
for (int i = 1; i <= n; ++i) {
int cur_bit = get_bit(i, bit);
if (t == 0) {
res[state][i] = encode(bit, cur_bit + 1);
} else {
int a_bit = t - 1;
int b_bit = get_bit(i, bit);
if (a_bit < b_bit) res[state][i] = -1;
else if (a_bit > b_bit) res[state][i] = -2;
else res[state][i] = encode(bit - 1, 0);
}
}
}
return res;
}
