#include <vector>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
vector<int> cap(21), take(21);
cap[0] = 2;
for (int k = 1; k <= 20; ++k) {
for (int r = 1; r <= k; ++r) {
int cur = r * cap[k - r] + 2;
if (cur > cap[k]) {
cap[k] = cur;
take[k] = r;
}
}
}
int K = 0;
while (cap[K] < N) ++K;
struct Level {
int k, r, start;
};
vector<Level> levels;
for (int k = K, start = 1; k > 0; ) {
int r = take[k];
levels.push_back({k, r, start});
start += r;
k -= r;
}
vector<vector<int>> s(K + 1, vector<int>(N + 1, 0));
auto cur_smaller = [](int bag) {
return bag == 0 ? -1 : -2;
};
auto prev_smaller = [](int bag) {
return bag == 0 ? -2 : -1;
};
auto symbol = [&](int k, int v) {
if (v == 1) return pair<int, int>{-1, 0};
if (v == cap[k]) return pair<int, int>{-2, 0};
int sub = cap[k - take[k]];
return pair<int, int>{(v - 2) / sub, (v - 2) % sub + 1};
};
auto suffix_value = [&](int level_index, int value) {
int v = value;
for (int p = 0; p < level_index; ++p) {
auto [sym, rem] = symbol(levels[p].k, v);
if (sym < 0) return sym == -1 ? 1 : cap[levels[level_index].k];
v = rem;
}
return v;
};
auto after_equal = [&](int level_index, int rem, int bag) {
if (level_index + 1 == (int)levels.size()) {
return rem == 1 ? cur_smaller(bag) : prev_smaller(bag);
}
const Level &next = levels[level_index + 1];
auto [sym, next_rem] = symbol(next.k, rem);
if (sym == -1) return cur_smaller(bag);
if (sym == -2) return prev_smaller(bag);
return next.start + sym;
};
s[0][0] = 0;
if (K == 0) {
for (int j = 1; j <= N; ++j) {
s[0][j] = (j == 1 ? -1 : -2);
}
return s;
}
for (int j = 1; j <= N; ++j) {
auto [sym, rem] = symbol(K, j);
if (sym == -1) s[0][j] = -1;
else if (sym == -2) s[0][j] = -2;
else s[0][j] = levels[0].start + sym;
}
for (int li = 0; li < (int)levels.size(); ++li) {
const Level &lv = levels[li];
int bag = (li + 1) % 2;
for (int g = 0; g < lv.r; ++g) {
int row = lv.start + g;
s[row][0] = bag;
for (int j = 1; j <= N; ++j) {
int v = suffix_value(li, j);
auto [sym, rem] = symbol(lv.k, v);
if (sym == -1) s[row][j] = cur_smaller(bag);
else if (sym == -2) s[row][j] = prev_smaller(bag);
else if (sym < g) s[row][j] = cur_smaller(bag);
else if (sym > g) s[row][j] = prev_smaller(bag);
else s[row][j] = after_equal(li, rem, bag);
}
}
}
return s;
}
