#include "prison.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
using namespace std;
vi tern(int x){
int cur = 1;
vi ret;
while(x > 0){
ret.pb(x % (cur * 3) / cur);
x -= (x % (cur * 3));
cur *= 3;
}
while(ret.size() < 8)ret.pb(0);
reverse(ret.begin(), ret.end());
return ret;
}
std::vector<std::vector<int>> devise_strategy(int N) {
vector<vi>v(25, vi(N+1));
v[0][0] = 0;
FOR(i, 1, N+1){
vi cur = tern(i);
v[0][i] = 1 + cur[0];
}
FOR(dig, 1, 8){
if(dig % 2 == 1){
v[dig * 3 - 2][0] = 1;
v[dig * 3 - 1][0] = 1;
v[dig * 3][0] = 1;
}
else{
v[dig * 3 - 2][0] = 0;
v[dig * 3 - 1][0] = 0;
v[dig * 3][0] = 0;
}
FOR(i, 1, N+1){
vi cur = tern(i);
f0r(j, 3){
if(cur[dig] < j){
v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -2 : -1);
}
else if(cur[dig] > j){
v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -1 : -2);
}
else{
v[(dig - 1) * 3 + 1 + j][i] = dig * 3 + 1 + cur[dig+1];
}
}
}
}
/*
f0r(i, 25){
f0r(j, 11)cout<<v[i][j]<<' ';
cout<<'\n';
}
*/
return v;
}
