#include "prison.h"
#include <vector>
#include <tuple>
#include <utility>
#include <map>
#include <cassert>
using namespace std;
using pii = pair<int, int>;
const int P[10] = {1, 3, 9, 27, 81, 243, 729, 2187};
const int A_SMALL = -1;
const int B_SMALL = -2;
vector<vector<int>> devise_strategy(int N) {
map<pii, int> M;
M[pii(0, 1)] = 1;
for(int i = 1; i <= 7; i++) {
int x = M.size() + 1;
M[pii(i, 0)] = x;
M[pii(i, 1)] = x+1;
M[pii(i, 2)] = x+2;
}
vector<vector<int>> ans(M.size() + 1, vector<int>(N + 1));
ans[0][0] = 0;
for(int i = 1; i <= N; i++) {
ans[0][i] = M[pii(7, i / P[7])];
}
for(auto [k, i] : M) {
auto [d, m] = k;
ans[i][0] = (d & 1 ? 1 : 0);
for(int c = 1; c <= N; c++) {
if (d == 0) {
ans[i][c] = (m == (c % P[1]) ? 0 : m < (c % P[1]) ? B_SMALL : A_SMALL);
continue;
}
int me_m = (c / P[d]) % P[1];
int me_small = (d & 1 ? B_SMALL : A_SMALL);
int me_big = (d & 1 ? A_SMALL : B_SMALL);
if (me_m == m) {
int me_nxt = (c / P[d-1]) % P[1];
if (d > 1) {
ans[i][c] = M[pii(d-1, me_nxt)];
} else {
if (me_nxt == 1) {
ans[i][c] = M[pii(d-1, me_nxt)];
} else {
ans[i][c] = (me_nxt == 2 ? me_big : me_small);
}
}
} else {
if (me_m < m) {
ans[i][c] = me_small;
} else {
ans[i][c] = me_big;
}
}
}
}
return ans;
}
