#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> devise_strategy(int N) {
vector<vector<int>> res;
vector<int> add(N + 1);
int mxBit = 32 - __builtin_clz(N);
// cout << mxBit << "\n";
add[0] = mxBit & 1;
add[1] = (add[0] ? -2 : -1);
add[N] = (add[0] ? -1 : -2);
for (int i = 2; i < N; ++i) {
add[i] = 2 - (i >> (mxBit - 1) & 1);
}
res.push_back(add);
for (int bit = mxBit - 1; bit >= 0; --bit) {
int idx = (mxBit - bit) * 2 - 1;
auto na = add;
int turn = bit & 1;
na[0] = turn;
na[1] = (turn ? -2 : -1);
na[N] = (turn ? -1 : -2);
for (int i = 2; i < N; ++i) {
if (i >> bit & 1) {
if (bit == 0) {
na[i] = 0; // impossible?
continue;
}
int turnon = (i >> (bit - 1)) & 1;
na[i] = idx + 3 - turnon;
} else {
na[i] = (turn ? -2 : -1);
}
}
res.push_back(na);
na = add;
na[0] = turn;
na[1] = (turn ? -2 : -1);
na[N] = (turn ? -1 : -2);
for (int i = 2; i < N; ++i) {
if (!(i >> bit & 1)) {
if (bit == 0) {
na[i] = 0; // impossible?
continue;
}
int turnon = (i >> (bit - 1)) & 1;
na[i] = idx + 3 - turnon;
} else {
na[i] = (turn ? -1 : -2);
}
}
res.push_back(na);
}
// for (auto& v : res) {
// for (auto& u : v) {
// cerr << u << " ";
// }
// cerr << "\n";
// }
// cerr << "\n";
return res;
}
