#include "prison.h"
#include "bits/stdc++.h";
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct pii{int a, b;};
int baseVal(int x, int b, int i) {
forR(j, i) x /= b;
return x % b;
}
std::vector<std::vector<int>> devise_strategy(int N) {
int base = 3;
int mb = 0;
forR(i, 20) if(baseVal(N, base, i)) mb = i;
vvi ret(base * (mb+1) + 1, vi(N+1));
ret[0][0] = 0;
REP(val, 1, N+1) {
ret[0][val] = baseVal(val, base, mb) + 1;
}
for(int i = mb; i >= 0; --i) {
int ordInd = mb - i;
int b0i = ordInd * base + 1;
REP(j, b0i, b0i + base) ret[j][0] = ordInd % 2 == 0 ? 1 : 0;
REP(val, 1, N+1) {
int cbt = baseVal(val, base, i);
REP(j, b0i, b0i + cbt) ret[j][val] = ordInd % 2 == 0 ? -1 : -2;
REP(j, b0i + cbt + 1, b0i + base) ret[j][val] = ordInd % 2 == 0 ? -2 : -1;
if(i > 0) {
ret[b0i + cbt][val] = b0i + base + baseVal(val, base, i-1);
}
}
}
// for(vi& i: ret) {
// for(int j : i) cout << j << ' ';
// cout << '\n';
// }
return ret;
}
