#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 rep1(a, b) for (int a = 1; 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;
using pii = pair<int, int>;
const int MOD = 1e9 + 7;
#define LOCAL true
const int STATES = 21;
const int MAX_N = 5000;
struct Node {
pii range;
vector<Node> children;
void expand(int depth) {
int selfsize = range.second - range.first + 1;
if (selfsize <= 2) return;
int cur_s = range.first + 1;
if (depth <= 6) { // split into 3
children = { Node{}, Node{}, Node{} };
int childsize = (selfsize-2) / 3;
int childsizemod = (selfsize-2) % 3;
rep(i, 3) {
if (childsizemod > 0) {
children[i].range = {cur_s, cur_s+childsize};
childsizemod--;
} else children[i].range = {cur_s, cur_s+childsize-1};
cur_s = children[i].range.second + 1;
children[i].expand(depth+1);
}
} else { // split into 2
children = { Node{}, Node{} };
int childsize = (selfsize-2) / 2;
int childsizemod = (selfsize-2) % 2;
if (childsizemod == 0) {
children[0].range = {cur_s, cur_s+childsize-1};
children[1].range = {cur_s+childsize, cur_s+childsize*2 - 1};
} else {
children[0].range = {cur_s, cur_s+childsize};
children[1].range = {cur_s+childsize+1, cur_s+childsize*2};
}
}
}
};
Node root;
const int LOWER_BOUND = -1337;
const int UPPER_BOUND = -4200;
vector<int> paths[MAX_N+7];
void calc_paths() {
Node* nodeptr;
rep1(val, MAX_N) {
nodeptr = &root;
while (true) {
if (val == nodeptr->range.first) {
paths[val].push_back(LOWER_BOUND);
break;
}
if (val == nodeptr-> range.second) {
paths[val].push_back(UPPER_BOUND);
break;
}
rep(i, nodeptr->children.size()) {
if (val <= nodeptr->children[i].range.second) {
paths[val].push_back(i);
nodeptr = &nodeptr->children[i];
break;
}
}
}
}
}
pii statetoboard[107];
map<pii, int> boardtostate;
void calc_trans() {
int s = 1;
rep1(depth, 6) {
rep(path, 3) {
pii board = {depth, path};
statetoboard[s] = board;
boardtostate[board] = s++;
}
}
statetoboard[s] = {7, 0};
boardtostate[{7, 0}] = s++;
statetoboard[s] = {7, 1};
boardtostate[{7, 1}] = s++;
}
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> strat = vector<vector<int>>(STATES, vector<int>(N+1, 0));
root.range = {1, 5000};
root.expand(1);
calc_paths();
calc_trans();
// board == 00
rep1(num, N) {
if (paths[num][0] == LOWER_BOUND) strat[0][num] = -1;
else if (paths[num][0] == UPPER_BOUND) strat[0][num] = -2;
else strat[0][num] = boardtostate[{1, paths[num][0]}];
}
rep1(x, STATES-1) {
pii board = statetoboard[x];
int layer = board.first;
int choice = board.second;
int same = (layer % 2 == 0 ? -1 : -2);
int other = (layer % 2 == 0 ? -2 : -1);
strat[x][0] = -same - 1;
rep1(num, N) {
if (paths[num].size() < layer) continue;
int numchoice = paths[num][layer-1];
int nextchoice;
if (paths[num].size() >= layer+1) nextchoice = paths[num][layer];
if (numchoice == LOWER_BOUND || numchoice < choice) strat[x][num] = same;
else if (numchoice == UPPER_BOUND || numchoice > choice) strat[x][num] = other;
else if (nextchoice == LOWER_BOUND) strat[x][num] = same;
else if (nextchoice == UPPER_BOUND) strat[x][num] = other;
else strat[x][num] = boardtostate[{layer+1, paths[num][layer]}];
}
}
return strat;
}
