#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define array_log(arr, x) {rep(y, x) {cout << arr[y] << ' ';} cout << '\n';}
#define unordered_map __gnu_pbds::gp_hash_table
using ll = long long;
const int MOD = 1e9 + 7;
#define LOCAL true
const int MAX_N = 5000 + 7;
const int MAX_X = 23;
int base3[MAX_N][9]; // idx od 1
int statetoboard[30];
int boardtostate[30];
void calc_base3() {
rep(i, MAX_N) {
if (i == 0) continue;
int num = i;
rep(di, 8) {
base3[i][8 - di] = num % 3;
num /= 3;
}
}
}
void calc_trans() {
int board = 1;
for (int state = 1; state < MAX_X; state++) {
statetoboard[state] = board;
boardtostate[board] = state;
if (board == 7) board += 3;
if (board == 18) board += 2;
board++;
}
}
vector<vector<int>> devise_strategy(int N) {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<vector<int>> strat = vector<vector<int>>(MAX_X, vector<int>(N+1, 0));
calc_base3();
calc_trans();
// board == 00
for (int num = 1; num <= N; num++) {
strat[0][num] = boardtostate[10*base3[num][1] + 1];
}
for (int state = 1; state < MAX_X; state++) {
int board = statetoboard[state];
int d = board / 10;
int i = board % 10;
strat[state][0] = i % 2;
int same = (i % 2 == 0 ? -1 : -2);
int other = (i % 2 == 0 ? -2 : -1);
for (int num = 1; num <= N; num++) {
int dthis = base3[num][i];
if (dthis < d) strat[state][num] = same;
else if (dthis > d) strat[state][num] = other;
else {
strat[state][num] = boardtostate[10*base3[num][i+1] + i+1];
if (i == 7) {
if (base3[num][8] == 0) strat[state][num] = same;
else if (base3[num][8] == 2) strat[state][num] = other;
}
}
}
}
return strat;
}
// int main()
// {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// if (LOCAL) {
// freopen("io/in", "r", stdin);
// freopen("io/out", "w", stdout);
// }
// int N = 5000;
// auto strat = devise_strategy(N);
// for (int state = 0; state < MAX_X; state++) {
// array_log(strat[state], N+1);
// }
// return 0;
// }
