#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> v;
int g (bool x, bool w) {
if (!x) {
return (w ? -2 : -1);
}
return (w ? -1 : -2);
}
void solve (int n, vector <int> a, vector <int> f, bool x) {
if (n == 5000) {
v.push_back({});
v.back().push_back(0);
int mid = (n - 1) / 2;
vector <int> na, nf;
for (int i = 0; i < (int)a.size(); i++) {
if (a[i] <= 1) {
v.back().push_back(-1);
nf.push_back(0);
na.push_back(-1);
} else if (a[i] >= n) {
v.back().push_back(-2);
nf.push_back(1);
na.push_back(5001);
} else if (a[i] <= mid + 1) {
v.back().push_back(1);
nf.push_back(0);
na.push_back(a[i] - 1);
} else {
v.back().push_back(2);
nf.push_back(1);
na.push_back((a[i] - 2) % mid + 1);
}
}
solve (mid, na, nf, !x);
} else if (n == 1) {
v.push_back({});
v.back().push_back(x);
for (int i = 0; i < (int)a.size(); i++) {
if (f[i] == 0) {
v.back().push_back(g(x, 0));
} else {
v.back().push_back(g(x, 1));
}
}
//cout << 'x' << endl;
} else {
vector <int> na, nf;
int mid = (n - 1) / 2;
for (int i = 0; i < (int)a.size(); i++) {
if (a[i] <= 1) {
nf.push_back(0);
na.push_back(-1);
} else if (a[i] >= n) {
nf.push_back(1);
na.push_back(5001);
} else if (a[i] <= mid + 1) {
nf.push_back(0);
na.push_back(a[i] - 1);
} else {
nf.push_back(1);
na.push_back((a[i] - 2) % mid + 1);
}
}
for (int k = 0; k < 2; k++) {
v.push_back({});
v.back().push_back(x);
for (int i = 0; i < (int)a.size(); i++) {
int w = 2;
if (n == 3)
w = 1;
if (((k == 1) && (f[i] == 0))) {
v.back().push_back(g(x, 0));
} else if (((k == 0) && (f[i] == 1))) {
v.back().push_back(g(x, 1));
} else if (a[i] <= 1) {
v.back().push_back(g(x, 0));
} else if (a[i] >= n) {
v.back().push_back(g(x, 1));
} else if (a[i] <= mid + 1) {
v.back().push_back((int)v.size() + 1 - k);
} else {
v.back().push_back((int)v.size() + w - k);
}
}
}
solve (mid, na, nf, !x);
}
}
std::vector<std::vector<int>> devise_strategy(int N) {
vector <int> a, f;
for (int i = 1; i <= 5000; i++) {
a.push_back(i);
f.push_back(0);
}
solve (5000, a, f, 0);
vector <vector <int>> vv;
for (int i = 0; i < (int)v.size(); i++) {
vv.push_back({});
for (int j = 0; j <= N; j++) {
vv[i].push_back(v[i][j]);
}
}
return vv;
}
