#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
const int M=27;
int seq[]={3,3,3,3,3,3,3,3,3};
int sum[]={0,3,6,9,12,15,18,21,24,27};
int f[M];
vector<vector<int>> ans;
int get_bit(int x,int i){i=7-i;while(i--)x/=3;return x%3;}
void Solve(int l,int r,int x){
// printf("l=%d r=%d x=%d\n",l,r,x);
ans[x][l]=(f[x]%2==0?-1:-2);
ans[x][r]=(f[x]%2==0?-2:-1);
if(l+1>=r)return;
map<int,vector<int>> mp;
for(int i=l+1;i<r;i++){
int b=get_bit(i,f[i]-1);
if(x==0){
ans[x][i]=b+1;
mp[1].push_back(i);
mp[2].push_back(i);
mp[3].push_back(i);
continue;
}
int p=x-sum[f[i]-1]-1;
int q=get_bit(i,f[i]-2);
if(p<q){
ans[x][i]=(f[x]%2==0?-1:-2);
continue;
}
if(p>q){
ans[x][i]=(f[x]%2==0?-2:-1);
continue;
}
ans[x][i]=(sum[f[x]-1]+1+b);
mp[ans[x][i]].push_back(i);
}
for(auto&p:mp){
int mn=1e9,mx=-1e9;
for(int x:p.second)mn=min(mn,x),mx=max(mx,x);
if(mn<=mx)Solve(mn,mx,p.first);
}
}
vector<vector<int>> devise_strategy(int N){
ans.resize(M);
for(int i=0;i<M;i++)ans[i].resize(N+1);
int ptr=0;
ans[0][0]=0;
for(int i=1;i<M;i++){
while(sum[ptr]<i)ptr++;
f[i]=ptr;
}
Solve(1,N,0);
return ans;
}
