#include "bits/stdc++.h"
#include "prison.h"
using namespace std;
int b3(int n, int pos){
for (int k = 0; k < pos - 1; k++) n /= 3;
return n % 3;
}
int encode(int n, int pos){
int d = b3(n, pos);
pos -= 1 + (d == 2);
return (d << 3) | pos;
}
pair<int, int> decode(int val){
int d = val >> 3;
int pos = (val & 7) + 1;
pos += d == 2;
return {d, pos};
}
vector<vector<int>> devise_strategy(int N){
vector<vector<int>> strategy;
for (int i = 0; i <= 22; i++) {
vector<int> J(N + 1);
if (i == 0){
J[0] = 1;
for (int j = 1; j <= N; j++) J[j] = encode(j, 8);
} else {
auto [p, pos] = decode(i);
J[0] = pos & 1;
for (int j = 1; j <= N; j++){
int c = b3(j, pos);
if (c < p) J[j] = -1 - pos % 2;
else if (c > p) J[j] = pos % 2 - 2;
else{
J[j] = encode(j, pos - 1);
if (pos == 2 && b3(j, 1) != 1) J[j] = ~((b3(j, 1) >> 1) ^ (pos % 2));
}
}
}
strategy.push_back(J);
}
return strategy;
}
