#include "prison.h"
using namespace std;
typedef pair<int, int> pii;
#include <bits/stdc++.h>
class range {
public:
int l, r;
int par;
int id;
range(int l, int r, int p, int i) : l(l), r(r), par(p), id(i) {}
range() {}
};
const int n = 5102;
const int x = 21;
int strat[21][n+1];
bool parity[21];
vector<int> ranges[22];
vector<range> range_list;
void make_strat() {
range_list.push_back(range(1, n, -1, 0));
ranges[0].push_back(0);
for (int i = 0; i <= 15; i++) {
int nxt_start = 3*((i+2)/3)+1;
parity[nxt_start] = parity[nxt_start+1] = parity[nxt_start+2] = !parity[i];
for (int v: ranges[i]) {
range r = range_list[v];
int sz = (r.r-r.l)/3;
range_list.push_back(range(r.l+1, r.l+sz, v, nxt_start));
range_list.push_back(range(r.l+sz+1, r.l+2*sz, v, nxt_start+1));
range_list.push_back(range(r.l+2*sz+1, r.l+3*sz, v, nxt_start+2));
ranges[nxt_start].push_back(range_list.size()-3);
ranges[nxt_start+1].push_back(range_list.size()-2);
ranges[nxt_start+2].push_back(range_list.size()-1);
}
}
for (int i = 16; i <= 18; i++) {
int nxt_start = 3*((i+2)/3)+1;
for (int v: ranges[i]) {
range r = range_list[v];
range_list.push_back(range(r.l+1, r.r-1, v, nxt_start));
ranges[nxt_start].push_back(range_list.size()-1);
}
}
parity[19] = !parity[18];
parity[20] = parity[18];
for (int v: ranges[19]) {
range r = range_list[v];
range_list.push_back(range(r.l+1, r.r-1, v, 20));
ranges[20].push_back(range_list.size()-1);
}
// for (int v: ranges[20]) {
// range r = range_list[v];
// cout << r.l << ' ' << r.r << '\n';
// }
strat[0][0] = 0;
strat[0][1] = -1;
strat[0][n] = -2;
for (int i = 1; i < 21; i++) {
fill(strat[i], strat[i]+n+1, 0);
strat[i][0] = parity[i];
for (int v: ranges[i]) {
range r = range_list[v];
for (int j = range_list[r.par].l; j <= r.l; j++)
strat[i][j] = -1-parity[i];
for (int j = r.r; j <= range_list[r.par].r; j++)
strat[i][j] = -2+parity[i];
for (int j = r.l; j <= r.r; j++) strat[range_list[r.par].id][j] = i;
}
}
}
vector<vector<int>> devise_strategy(int N) {
make_strat();
vector<vector<int>> res(21, vector<int>(N+1));
for (int i = 0; i < 21; i++) {
for (int j = 0; j <= N; j++) res[i][j] = strat[i][j];
}
return res;
}
