#include "prison.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll INF=1LL<<60;
std::vector<std::vector<int>> devise_strategy(int N) {
vector<int> pows={1};
rep(i,10)pows.emplace_back(pows.back()*3);
vector<vector<int>> ret(30,vector<int>(N+1));
rep(i,8) {
ret[i*4][0]=0;
rng(j,1,N+1) {
int now=(j/pows[7-i])%3;
if(i==7) {
if(now==0)ret[i*4][j]=-1;
if(now==2)ret[i*4][j]=-2;
if(now==1)ret[i*4][j]=29;
}
else {
ret[i*4][j]=i*4+now+1;
}
}
if(i==7)break;
rep(j,3) {
int ind=i*4+j+1;
ret[ind][0]=1;
rng(k,1,N+1) {
int now=(k/pows[7-i])%3;
if(now==j)ret[ind][k]=(i+1)*4;
if(now<j)ret[ind][k]=-2;
if(now>j)ret[ind][k]=-1;
}
}
}
ret[29][0]=1;
rng(i,1,N+1) {
int now=i%3;
if(now==0)ret[29][i]=-2;
else ret[29][i]=-1;
}
return ret;
}
