#include <bits/stdc++.h>
using namespace std;
#include "prison.h"
int MAXNUM = 22;
int pow3[8] = {1, 3, 9, 27, 81, 243, 729, 2187};
vector<vector<int>> devise_strategy(int N){
vector<vector<int>> res(MAXNUM + 1, vector<int>(N+1));
for (int i = 0; i <= MAXNUM; i++){
int type = (i + 2) / 3;
int AB = type & 1;
res[i][0] = AB;
int cntbit[2] = {type, type};
if (type) cntbit[AB]--;
int oldbit = (i + 2) % 3;
for (int j = 1; j <= N; j++){
if (i == 0){
res[i][j] = (j / pow3[7]) % 3 + 1;
}
else if (i == 22){
int bit1 = j % 3;
if (bit1 == 0) res[i][j] = -1;
else res[i][j] = -2;
}
else if (i >= 19){
int bit1 = (j / 3) % 3, bit2 = j % 3;
if (bit1 < oldbit) res[i][j] = (AB ? -2 : -1);
else if (bit1 > oldbit) res[i][j] = (AB ? -1 : -2);
else if (bit2 == 0) res[i][j] = -2;
else if (bit2 == 2) res[i][j] = -1;
else res[i][j] = 22;
}
else{
int bit1 = (j / pow3[7 - cntbit[AB]]) % 3, bit2 = (j / pow3[6 - cntbit[AB]]) % 3;
if (bit1 < oldbit) res[i][j] = (AB ? -2 : -1);
else if (bit1 > oldbit) res[i][j] = (AB ? -1 : -2);
else{
res[i][j] = ((type + 1) * 3 - 2) + bit2;
}
}
}
}
return res;
}
