#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
void solve (int id, int d, int p, int l1, int r1, int l, int r, vector<vector<int>> &ans) {
int cur = d * 3 + p;
for (int i = l; i <= r; i++) {
ans[id][i] = cur;
}
// cout << ' ' << id << ' ' << d << ' ' << p << ' ' << l1 << ' ' << r1 << ' ' << l << ' ' << r << ' ' << cur << endl;
for (int i = l1; i <= l; i++) {
if (ans[cur][0] == 0) ans[cur][i] = -1;
else ans[cur][i] = -2;
}
for (int i = r; i <= r1; i++) {
if (ans[cur][0] == 0) ans[cur][i] = -2;
else ans[cur][i] = -1;
}
l++, r--;
if (l > r) return;
if (r - l < 2) {
// cout << l << ' ' << r << endl;
solve(cur, d + 1, 1, l - 1, r + 1, l, r, ans);
return;
}
if (r - l < 4) {
int mid = l + r >> 1;
solve(cur, d + 1, 1, l - 1, r + 1, l, mid, ans);
solve(cur, d + 1, 2, l - 1, r + 1, mid + 1, r, ans);
return;
}
int m1, m2;
m1 = (2 * l + r) / 3;
m2 = (l + 2 * r) / 3;
solve(cur, d + 1, 1, l - 1, r + 1, l, m1, ans);
solve(cur, d + 1, 2, l - 1, r + 1, m1 + 1, m2, ans);
solve(cur, d + 1, 3, l - 1, r + 1, m2 + 1, r, ans);
}
vector<vector<int>> devise_strategy (int n) {
vector<vector<int>> ans(21, vector<int>(n + 1));
ans[0][0] = 1;
for (int i = 1, h = 0; i + 2 <= 20; i += 3, h ^= 1) {
ans[i][0] = ans[i + 1][0] = ans[i + 2][0] = h;
}
solve(0, -1, 3, 1, n, 1, n, ans);
return ans;
}
