#include <bits/stdc++.h>
using namespace std;
const int base = 3;
const int mp = 8;
int nth_bit(int x, int n){
if (n<0) return 0;
vector<int> wr;
while (x) {
wr.push_back(x % base);
x/= base;
}
wr.resize(mp+2, 0);
return wr[n];
}
std::vector<std::vector<int>> devise_strategy(int N){
vector ans(mp*base+1, vector (N+1, 0));
ans[0][0] = 0;
for (int i = 1; i <= N; i++) {
int bit = nth_bit(i, mp - 1);
ans[0][i] = bit + 1;
}
for (int i=1; i <= mp*base; i++) {
int r = (i-1)/base % 2;
ans[i][0] = !r;
int this_bit = (i-1) % base;
for (int j=1; j<=N; j++) {
int other_bit = nth_bit(j, mp - 1 - (i-1)/base);
int new_bit = nth_bit(j, mp - 2 - (i-1)/base);
if (this_bit < other_bit) ans[i][j] = -1 - r;
if (this_bit > other_bit) ans[i][j] = -1 - !r;
if (this_bit == other_bit) ans[i][j] = ((i-1)/base + 1) * base + 1 + new_bit;
if (ans[i][j] > mp*base) ans[i][j] = -1;
}
}
return ans;
}
