#include <bits/stdc++.h>
#include "prison.h"
#define ll long long
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b ) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b ) { return a < b ? a = b, 1 : 0; }
std::vector<std::vector<int>> devise_strategy(int N) {
int req = 0, cur = 1;
while (cur < N) cur *= 3, req++;
// req bits
// [1, N]
vector<vector<int>> ans(req*4+1, vector<int>(N+1));
auto split = [&](int x) {
vector<int> res;
while (x) {
res.push_back(x % 3);
x /= 3;
}
while (sz(res) < req) res.emplace_back(0);
reverse(all(res));
return res;
};
vector<vector<int>> val(N);
for (int i = 0; i < N; i++) val[i] = split(i);
for (int i = 0; i <= req*4; i++) {
if (!i) {
ans[i][0] = 0;
for (int j = 1; j <= N; j++) ans[i][j] = (req - 1) * 4 + 1;
}
else {
int bit = req - ((i - 1) / 4) - 1;
if (i % 4 == 1) {
// we look 1
ans[i][0] = 0;
for (int j = 1; j <= N; j++) {
ans[i][j] = i + val[j-1][bit] + 1;
}
}
else {
ans[i][0] = 1;
int v = i % 4 == 2 ? 0 : i % 4 == 3 ? 1 : 2;
for (int j = 1; j <= N; j++) {
if (val[j-1][bit] != v) {
ans[i][j] = val[j-1][bit] < v ? -2 : -1;
}
else {
ans[i][j] = (i - 1) / 4 == 0 ? 0 : ((i - 1) / 4 - 1) * 4 + 1;
}
}
}
}
}
return ans;
}
