#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> ans;
const int mxbit = 7;
int pw[mxbit + 3];
int n;
void rec(int bit, int a, int i){
if(bit & 1){
ans[i][0] = 1;
for(int j = 1; j <= n; j++){
int b = (j / pw[bit]) % 3;
if(b > a) ans[i][j] = -2;
else if(b < a) ans[i][j] = -1;
else{
if(bit == 0) return;
bit--;
b = (j / pw[bit] % 3);
ans[i][j] = bit * 3 + b;
rec(bit, b, ans[i][j]);
}
}
}
else{
ans[i][0] = 0;
for(int j = 1; j <= n; j++){
int b = (j / pw[bit]) % 3;
if(b > a) ans[i][j] = -1;
else if(b < a) ans[i][j] = -2;
else{
if(bit == 0) return;
bit--;
b = (j / pw[bit] % 3);
ans[i][j] = bit * 3 + b;
rec(bit, b, ans[i][j]);
}
}
}
}
vector<vector<int>> devise_strategy(int N){
n = N;
ans.resize(mxbit * 3);
for(auto& a : ans) a.resize(N + 1, 0);
pw[0] = 1;
for(int i = 1; i <= mxbit; i++) pw[i] = pw[i - 1] * 3;
ans[0][0] = 0;
for(int j = 1; j <= n; j++){
ans[0][j] = mxbit * 3 + (j / pw[mxbit] % 3);
}
rec(mxbit, 0, mxbit * 3);
rec(mxbit, 1, mxbit * 3 + 1);
rec(mxbit, 2, mxbit * 3 + 2);
return ans;
}
