#include <bits/stdc++.h>
#include "prison.h"
// #include "grader.cpp"
using namespace std;
int digit(int x, int i){
for (int j = 0; j < 7 - i; j ++)
x /= 3;
return x % 3;
}
int ceil(int x, int y){
return (x / y + ((x % y) > 0));
}
vector<vector<int>> devise_strategy(int n) {
vector<vector<int>> res;
res.resize(23);
for (int i = 0; i < 23; i ++){
res[i].resize(n + 1);
if (ceil(i, 3) % 2 == 0) res[i][0] = 0;
else res[i][0] = 1;
if (i == 22){
for (int j = 1; j <= n; j ++){
if (j % 3 == 0)
res[i][j] = -1 -(ceil(i, 3) % 2);
else
res[i][j] = -3 -(-1 -(ceil(i, 3) % 2));
}
break;
}
int cur = ceil(i, 3);
// cout << i << " :: " << res[i][0] << " " << cur << endl;
for (int j = 1; j <= n; j ++){
int nxt = digit(j, cur);
// cout << "put digit = " << nxt << endl;
if (cur == 0){
res[i][j] = 1 + nxt;
continue;
}
int pw = 1;
for (int jj = 0; jj < 8 - cur; jj ++, pw *= 3);
int curd = digit(j, cur - 1);
int rem = j % pw;
int prvd = (i - 1) % 3;
if (curd < prvd or (curd == prvd and rem == 0))
res[i][j] = -1 -(ceil(i, 3) % 2);
else if (curd > prvd or (curd == prvd and rem == pw - 1))
res[i][j] = -3 -(-1 -(ceil(i, 3) % 2));
else
res[i][j] = 1 + nxt + 3 * cur;
// cout << j << " : " << res[i][j] << endl;
if (res[i][j] == 23) res[i][j] = 22;
}
}
return res;
}
