/* https://ioi2022.id/data/editorial.pdf */
#include "prison.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 5000, K = 20, L = 9;
int max(int a, int b) { return a > b ? a : b; }
int nn[K + 1], cc[K + 1], kk[L + 1], dd[N + 1][L];
void init() {
nn[0] = 2;
for (int k = 1; k <= K; k++)
for (int c = 1; c <= k; c++) {
int n = nn[k - c] * c + 2;
if (nn[k] < n)
nn[k] = n, cc[k] = c;
}
int l = 0;
for (int k = K; k > 0; k -= cc[k])
kk[l++] = k;
kk[l++] = 0;
for (int i = 1; i <= N; i++)
for (int h = 0, i_ = i - 1; h < l; h++) {
int k = kk[h], k_ = kk[h + 1];
if (i_ == 0) {
dd[i][h] = -1;
break;
} else if (i_ == nn[k] - 1) {
dd[i][h] = cc[k];
break;
} else {
dd[i][h] = (i_ - 1) / nn[k_];
i_ = (i_ - 1) % nn[k_];
}
}
}
vector<vi> devise_strategy(int n) {
init();
vector<vi> ttt;
for (int g = 0, h = 1; g <= L; g++) {
int c = g == 0 ? 1 : cc[kk[g - 1]], c_ = cc[kk[g]];
for (int d = 0; d < c; d++) {
vi tt(n + 1, 0);
tt[0] = g % 2;
for (int i = 1; i <= n; i++)
if (g > 0 && dd[i][g - 1] != d)
tt[i] = (g % 2 == 0) == (dd[i][g - 1] < d) ? -1 : -2;
else if (dd[i][g] == -1)
tt[i] = g % 2 == 0 ? -1 : -2;
else if (dd[i][g] == c_)
tt[i] = g % 2 != 0 ? -1 : -2;
else
tt[i] = h + dd[i][g];
ttt.push_back(tt);
}
h += c_;
}
return ttt;
}
