#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int n) {
if (n==2) {
vector<vector<int>> ans = {{0,-1,-2},{1,-2,-1}};
return ans;
}
int x = 3 * ceil(log2(n)/(float(log2(3)))) - 2; //cout << x << "\n";
vector<vector<int>> ans(x+1,vector<int>(n+1));
vector<int> p3 = {1};
while (p3.back() < n) {
p3.push_back(3*p3.back());
}
int bggest = 0;
int cp = n;
while (cp>0) {
bggest++;
cp/=3;
}
vector<vector<int>> b3(n+1,vector<int>(bggest));
for (int i=0;i<=n;i++) {
int j = 0,k=i;
while (k>0) {
b3[i][j] = k%3;
k/=3; j++;
}
reverse(b3[i].begin(),b3[i].end());
}
ans[0][0] = 0;
for (int j=1;j<=n;j++) {
ans[0][j] = 1 + b3[j][0];
}
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-1)%3) {
int value = 3*step + b3[j][step]+1;
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-1)%3) {
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;
}
}
}
}
}
return ans;
}
