#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> blocksize;
vector<vector<int>> block;
/*
0) 5000 -> 1666
1) 1666 -> 555
2) 555 -> 185
3) 185 -> 61
4) 61 -> 20
5) 20 -> 9
6) 9 -> 4
7) 4 -> 2
8) 2 -> 1
*/
const int MAX_CAN = 5000;
void genblock(int l = 1, int r = MAX_CAN, int ly = 0) {
while (blocksize.size() <= ly) blocksize.push_back(0);
while (block.size() <= ly) block.push_back(vector<int>(MAX_CAN+1));
if (ly <= 4) {
blocksize[ly] = 3;
int e1 = l+(r-l)/3;
int e2 = l+2*(r-l)/3;
for (int i = l+1; i <= e1; i++) block[ly][i] = 0;
for (int i = e1+1; i <= e2; i++) block[ly][i] = 1;
for (int i = e2+1; i < r; i++) block[ly][i] = 2;
block[ly][l] = -1;
block[ly][r] = -2;
genblock(l+1, e1, ly+1);
genblock(e1+1, e2, ly+1);
genblock(e2+1, r-1, ly+1);
} else if (ly <= 6) {
blocksize[ly] = 2;
int e = (l+r)/2;
for (int i = l+1; i <= e; i++) block[ly][i] = 0;
for (int i = e+1; i < r; i++) block[ly][i] = 1;
block[ly][l] = -1;
block[ly][r] = -2;
genblock(l+1, e, ly+1);
genblock(e+1, r-1, ly+1);
} else if (ly == 7) {
blocksize[ly] = 1;
for (int i = l+1; i < r; i++) block[ly][i] = 0;
block[ly][l] = -1;
block[ly][r] = -2;
genblock(l+1, r-1, ly+1);
} else if (ly == 8) {
blocksize[ly] = 0;
block[ly][l] = -1;
block[ly][r] = -2;
}
}
vector<vector<int>> devise_strategy(int _N) {
N = _N;
genblock();
int x = 20;
vector<vector<int>> ret(x+1, vector<int>(N+1));
// First play
ret[0][0] = 0;
for (int i = 1; i <= N; i++) ret[0][i] = 1 + block[0][i];
ret[0][1] = -1;
ret[0][N] = -2;
// Other plays
vector<vector<int>> state_description = {
{-1, 0},
{0, 0},
{0, 1},
{0, 2},
{1, 0},
{1, 1},
{1, 2},
{2, 0},
{2, 1},
{2, 2},
{3, 0},
{3, 1},
{3, 2},
{4, 0},
{4, 1},
{4, 2},
{5, 0},
{5, 1},
{6, 0},
{6, 1},
{7, 0}
};
for (int j = 1; j <= 20; j++) {
int from_layer = state_description[j][0];
int from_block = state_description[j][1];
int cur_player = 1 - from_layer%2;
ret[j][0] = cur_player;
for (int i = 1; i <= N; i++) {
int to_layer = from_layer+1;
int to_block = block[to_layer][i];
int cur_block = block[from_layer][i];
if (i == 1) ret[j][i] = -1 - cur_player;
else if (i == N) ret[j][i] = -1 - (1-cur_player);
else if (cur_block == -1) ret[j][i] = -1 - cur_player;
else if (cur_block == -2) ret[j][i] = -1 - (1-cur_player);
else if (cur_block < from_block) ret[j][i] = -1 - cur_player;
else if (from_block < cur_block) ret[j][i] = -1 - (1-cur_player);
else if (to_block == -1) ret[j][i] = -1 - cur_player;
else if (to_block == -2) ret[j][i] = -1 - (1-cur_player);
else {
vector<int> to_find = {to_layer, to_block};
int idx = find(state_description.begin(), state_description.end(), to_find) - state_description.begin();
if (idx <= x) ret[j][i] = idx;
else ret[j][i] = -1;
}
}
}
return ret;
}
