#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
int k = 0;
while ((1 << k) <= N) k++;
k--;
int k2 = k - 1;
vector<vector<int>> ans(k2 * 2 + 3, vector<int> (N + 1));
ans[0][0] = 0;
for (int i = 1; i <= N; i++) {
if (i >> k & 1) ans[0][i] = 2;
else ans[0][i] = 1;
}
for (int i = 1; i <= k2 * 2 + 2; i++) {
int b = k - (i - 1) / 2, v = (i - 1) & 1;
if ((k - b) & 1) {
ans[i][0] = 0;
for (int j = 1; j <= N; j++) {
if (j >> b & 1) {
if (!v) ans[i][j] = -2;
}else {
if (v) ans[i][j] = -1;
}
if (b && !ans[i][j]) {
if (b == 1) {
if (j & 1) ans[i][j] = -2;
else ans[i][j] = -1;
continue;
}
if (j >> (b - 1) & 1) ans[i][j] = (k + 1 - b) * 2 + 2;
else ans[i][j] = (k + 1 - b) * 2 + 1;
}
}
continue;
}
ans[i][0] = 1;
for (int j = 1; j <= N; j++) {
if (j >> b & 1) {
if (!v) ans[i][j] = -1;
}else {
if (v) ans[i][j] = -2;
}
if (b && !ans[i][j]) {
if (b == 1) {
if (j & 1) ans[i][j] = -1;
else ans[i][j] = -2;
continue;
}
if (j >> (b - 1) & 1) ans[i][j] = (k + 1 - b) * 2 + 2;
else ans[i][j] = (k + 1 - b) * 2 + 1;
}
}
}
return ans;
}
