#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int get_bit(int N, int i) {
while (i--) N /= 3;
return N % 3;
}
vector<vector<int>> devise_strategy(int N) {
int X = 22;
vector<vector<int>> S(X + 1, vector<int>(N + 1, 0));
S[0][0] = 0;
for (int i = 1; i <= N; i++)
S[0][i] = 1 + get_bit(i, 7);
for (int i = 1; i <= X - 1; i++) {
int k = (i - 1) / 3;
int pos = 7 - k;
int a = (i - 1) % 3;
S[i][0] = (k % 2 == 0);
for (int j = 1; j <= N; j++) {
int b = (get_bit(j, pos));
if (a != b) {
if (a < b)
S[i][j] = (S[i][0] ? -1 : -2);
else
S[i][j] = (S[i][0] ? -2 : -1);
} else {
if (pos > 1) {
S[i][j] = (k + 1) * 3 + 1 + get_bit(j, pos - 1);
}
else {
if (get_bit(j, pos - 1) == 0)
S[i][j] = (S[i][0] ? -2 : -1);
if (get_bit(j, pos - 1) == 2)
S[i][j] = (S[i][0] ? -1 : -2);
if (get_bit(j, pos - 1) == 1)
S[i][j] = 22;
}
}
}
}
S[22][0] = 0;
for (int i = 1; i <= N; i++) {
int b = get_bit(i, 0);
if (b == 0) S[22][i] = -1;
if (b == 2) S[22][i] = -2;
if (b == 1) S[22][i] = 0;
}
return S;
}
