#include "prison.h"
#include <iostream>
using namespace std;
int get(int x, int ind) {
while (ind--)
x /= 3;
return x % 3;
}
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> ans(N + 1);
for (auto& it : ans) {
it.resize(N + 1);
}
if (N <= 22) {
for (int i = 0; i <= N; i++) {
if (i == 0) ans[i][0] = 0;
else ans[i][0] = 1;
for (int j = 1; j <= N; j++) {
if (i) {
if (j > i) ans[i][j] = -1;
else ans[i][j] = -2;
}
else ans[i][j] = j;
}
}
return ans;
}
else {
ans[0][0] = 0;
for (int j = 1; j <= N; j++) {
ans[0][j] = get(j, 7) + 1;
}
for (int i = 1; i <= 21; i++) {
int ind = (i - 1) / 3;
int last_dig = (i - 1) % 3;
if (ind % 2 == 0) ans[i][0] = 1;
else ans[i][0] = 0;
for (int j = 1; j <= N; j++) {
int cur_last_dig = get(j, 7 - ind);
if (cur_last_dig > last_dig) ans[i][j] = (ans[i][0] == 1) ? -2 : -1;
else if (cur_last_dig < last_dig) ans[i][j] = (ans[i][0] == 0) ? -2 : -1;
else {
if (ind < 6) ans[i][j] = (ind + 1) * 3 + get(j, 6 - ind) + 1;
else {
if (get(j, 6 - ind) == 2) ans[i][j] = (ans[i][0] == 1) ? -2 : -1;
if (get(j, 6 - ind) == 0) ans[i][j] = (ans[i][0] == 0) ? -2 : -1;
if (get(j, 6 - ind) == 1) ans[i][j] = 22;
}
}
}
}
ans[22][0] = 0;
for (int j = 1; j <= N; j++) {
if (j % 3 == 0) ans[22][j] = -2;
else ans[22][j] = -1;
}
for (int i = 0; i <= 22; i++) {
for (int j = 0; j <= N; j++) {
if (ans[i][j] < 0) ans[i][j] = -3 - ans[i][j];
}
}
return ans;
}
}
