#include "prison.h"
#include <vector>
using namespace std;
int ithidk(int n,int ind){
while(ind--)
n/=3;
return n%3;
}
int pw[10];
int lstidk(int n,int ind){
return n % pw[ind];
}
vector<int> which_to_do(int num,int n){
vector<int>res(n+1);
res[0]=(num+2)/3&1;
int BBit=8-(num+2)/3,vl=(num-1)%3;
if(!num)
for(int i=1;i<=n;i++)
res[i]=ithidk(i,7)+1;
else for(int i=1;i<=n;i++) {
int c=ithidk(i,BBit);
if(c<vl)res[i]=-res[0]-1;
else if(c>vl)res[i]=-!res[0]-1;
else { int K=lstidk(i,BBit);
if(K==0) res[i]=-res[0]-1;
else if(K==pw[BBit]-1)
res[i]=-!res[0]-1;
else res[i]=min(22,ithidk(i,BBit-1)+1+(num+2)/3*3);
}
}
return res;
}
vector<int>finale(int n){
vector<int>res(n+1);
for(int i=1;i<=n;i++)
res[i]=(i%3?-2:-1);
return res;
}
vector<vector<int>> devise_strategy(int N) {
pw[0]=1;
for(int i=1;i<10;i++)
pw[i]=pw[i-1]*3;
vector<vector<int>> ans;
for(int i=0;i<22;i++)
ans.push_back(which_to_do(i,N));
ans.push_back(finale(N));
return ans;
}
