#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int n) {
int x = 3 * (log2(n)/(float(log2(3)))) - 2;
vector<vector<int>> ans(x+1,vector<int>(n+1));
vector<int> p3 = {1};
while (p3.back() < n) {
p3.push_back(3*p3.back());
}
vector<vector<int>> b3(n+1,vector<int>(8));
for (int i=0;i<=n;i++) {
int j = 0,k=i;
while (k>0) {
b3[i][j] = k%3;
k/=3; j++;
}
}
ans[0][0] = 0;
for (int j=1;j<=n;j++) {
ans[0][j] = (j-1)%3+1;
}
for (int i=1;i<=x;i++) {
int step = ceil(i/3.00);
if (step%2 == 0) {
ans[i][0] = 0;
} else {
ans[i][0] = 1;
}
for (int j=1;j<=n;j++) {
if (i==x) {
if (b3[j][step-1] == 0) {
if (step%2==0) {
ans[i][j] = -1;
} else {
ans[i][j] = -2;
}
} else {
if (step%2==0) {
ans[i][j] = -2;
} else {
ans[i][j] = -1;
}
}
} else if (b3[j][step-1] == i%3) {
int value = 3*step + b3[j][step];
if (value == x) {
if (step%2==0) {
ans[i][j] = -1;
} else {
ans[i][j] = -2;
}
} else if (value == x+2){
if (step%2==0) {
ans[i][j] = -2;
} else {
ans[i][j] = -1;
}
} else if (value == x+1) {
ans[i][j] = x;
} else {
ans[i][j] = value;
}
} else {
if (b3[j][step-1] < i%3) {
if (i%2==0) {
ans[i][j] = -1;
} else {
ans[i][j] = -2;
}
} else {
if (i%2==0) {
ans[i][j] = -2;
} else {
ans[i][j] = -1;
}
}
}
}
}
return ans;
}
