#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> devise_strategy(int n) {
///ios::sync_with_stdio(0); cin.tie(0);
vector<int> dp(n + 1), par(n + 1, 0);
for (int i = 0; i <= n; i++) {
if (i <= 2) {
dp[i] = 0;
continue;
}
dp[i] = i;
for (int j = 1; j <= (i - 2); j++) {
dp[i] = min(dp[i], dp[j] + ((i - 2 + j - 1) / j));
if (dp[j] + ((i - 2 + j - 1) / j) == dp[i]) {
par[i] = j;
}
}
assert(par[i]);
}
int x = dp[n];
vector<int> dims;
vector<vector<int>> what(x + 1, vector<int> (n + 1, 0));
{
int current = n;
while (current >= 3) {
dims.push_back(current);
current = par[current];
}
dims.push_back(current);
///reverse(dims.begin(), dims.end());
}
/// cout << "dims = ";
/**for (int i = 0; i + 1 < (int) dims.size(); i++) {
cout << i << " ---> " << dims[i] << " " << par[dims[i]] << " " << ((dims[i] - 2 + dims[i + 1] - 1) / (dims[i + 1])) << "\n";
}
exit(0);**/
{
int sum_test = 0;
for (int i = 0; i + 1 < (int) dims.size(); i++) {
sum_test += ((dims[i] - 2 + dims[i + 1] - 1) / (dims[i + 1]));
}
assert(sum_test == x);
}
vector<int> position(x + 1, 0);
map<int, int> child;
int current = 0;
position[current++] = 0;
for (int i = 0; i + 1 < (int) dims.size(); i++) {
int now_len = dims[i];
int new_len = dims[i + 1];
int times = ((now_len - 2) + (new_len - 1)) / (new_len);
for (int j = 1; j <= times; j++) {
position[current++] = i + 1;
}
}
for (int i = 0; i <= x; i++) {
///cout << i << " : " << position[i] << "\n";
}
///exit(0);
function<void(int, int, int, int)> dfs = [&] (int state, int turn, int l, int r) {
if (l > r) {
return;
}
what[state][0] = turn;
/// cout << state << " " << turn << " " << l << " " << r << "\n";
if (turn == 1) {
for (int j = 1; j <= n; j++) {
if (j < l) {
what[state][j] = -2;
}
if (j > r) {
what[state][j] = -1;
}
}
} else {
for (int j = 1; j <= n; j++) {
if (j < l) {
what[state][j] = -1;
}
if (j > r) {
what[state][j] = -2;
}
}
}
if (l == r) {
return;
}
///cout << state << " " << turn << " : " << l << " " << r << "\n";
assert(l + 1 <= r);
assert(turn == 0 || turn == 1);
assert(0 <= state && state <= x);
assert(0 <= position[state] && position[state] <= (int) dims.size());
assert(r - l + 1 <= dims[position[state]]);
if (turn == 0) {
what[state][l] = -1;
what[state][r] = -2;
} else {
what[state][l] = -2;
what[state][r] = -1;
}
if (l + 1 <= r - 1) {
int st = l + 1, dr = r - 1;
assert(position[state] + 1 < (int) dims.size());
int last = state;
while (last + 1 < (int) position.size() && position[last + 1] == position[last]) {
last++;
}
int now_len = dims[position[state]];
int new_len = dims[position[state] + 1];
int times = ((now_len - 2) + (new_len - 1)) / (new_len);
for (int iter = 1; iter <= times; iter++) {
int l2 = st, r2 = min(dr, st + new_len - 1);
assert(position[last + iter] == position[state] + 1);
for (int num = l2; num <= r2; num++) {
what[state][num] = last + iter;
}
dfs(last + iter, turn ^ 1, l2, r2);
st = r2 + 1;
}
assert(st == dr + 1);
}
};
dfs(0, 0, 1, n);
return what;
for (int num = 0; num <= x; num++) {
}
assert(current == x + 1);
/// cout << "\n";
/// exit(0);
for (int i = 0; i <= x; i++) {
/// cout << i << " : " << position[i] << "\n";
/// cout << i << " ---> " << sum[i] << " " << position[i] << "\n";
}
///exit(0);
/// la inceput ce fac? citesc A-ul
/** int sum = 0;
what[0][0] = 0;
for (int val_a = 1; val_a <= n; val_a++) {
if (val_a == 1) {
what[0][val_a] = -1;
continue;
}
if (val_a == n) {
what[0][val_a] = -2;
continue;
}
int j = dims[1];
int delta_val_a = val_a - (2);
int id = delta_val_a / j;
what[0][val_a] = sum + 1 + id;
}*/
return what;
}
