#include "prison.h"
#include "bits/stdc++.h"
using namespace std;
#include <vector>
std::vector<std::vector<int>> devise_strategy(int N);
int bit(int n, int b) {
int p = 1;
for(int i=0; i<b; i++) p *= 3;
n %= (3 * p);
return n / p;
}
std::vector<std::vector<int>> devise_strategy(int N) {
int x = 22;
vector<vector<int> > ans;
// each array inside should hv length = N + 1
ans.resize(x + 1);
for(int i=0; i<=x; i++) ans[i].resize(N + 1);
ans[0][0] = 0;
for(int i=1; i<=N; i++) ans[0][i] = bit(i, 7) + 1;
for(int i=7; i>=1; i--) {
for(int j=(7-i) * 3 + 1; j<=(7-i) * 3 + 3; j++) {
ans[j][0] = i % 2;
int cc = j - (7-i) * 3 - 1;
for(int k=1; k<=N; k++) {
int bb = bit(k, i);
if(bb > cc) ans[j][k] = (i % 2 ? -1 : -2);
else if(bb < cc) ans[j][k] = (i % 2 ? -2 : -1);
else {
ans[j][k] = min(x, (8-i) * 3 + bit(k, i-1) + 1);
if(i == 1 && bit(k, 0) == 2) ans[j][k] = -1;
else if(i == 1 && bit(k, 0) == 0) ans[j][k] = -2;
}
}
}
}
// Hardcode 22
ans[22][0] = 0;
for(int i=1; i<=N; i++) {
int bb = bit(i, 0);
if(bb > 1) ans[22][i] = -2;
else ans[22][i] = -1;
}
return ans;
}
