#include "prison.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
struct tri {
int l1, r1;
int l2, r2;
};
int cnt = 1;
vector<pair<int, vector<tri>>> sym = {{0, {{1, 5589, 1, 5589}}}};
const int divvs = 8;
int divv[divvs] = {3, 3, 3, 3, 3, 2, 2, 1};
//vector<pair<int, vector<tri>>> sym = {{0, {{1, 11, 1, 11}}}};
//const int divvs = 2;
//int divv[divvs] = {2, 1};
const int m = 21;
std::vector<std::vector<int>> devise_strategy(int N) {
vector<tri> vlst = sym[0].second;
for (int j = 0;; ++j) {
//cout << j << ' ' << vlst.size() << '\n';
if (j >= divvs)
break;
int k = divv[j];
vector<vector<tri>> vec(k);
vector<tri> nlst;
for (auto [l1, r1, l2, r2] : vlst) {
if (j&1) {
l2 = max(l2, l1+1);
r2 = min(r2, r1-1);
if (l2 >= r2)
continue;
assert((r2 - l2)%k == 0);
int len = (r2 - l2) / k;
for (int p = 0; p < k; ++p) {
vec[p].push_back({l1, r1, l2 + p*len, l2 + (p+1)*len});
nlst.push_back({l1, r1, l2 + p*len, l2 + (p+1)*len});
}
} else {
l1 = max(l1, l2+1);
r1 = min(r1, r2-1);
if (l1 >= r1)
continue;
assert((r1 - l1)%k == 0);
int len = (r1 - l1) / k;
for (int p = 0; p < k; ++p) {
vec[p].push_back({l1 + p*len, l1 + (p+1)*len, l2, r2});
nlst.push_back({l1 + p*len, l1 + (p+1)*len, l2, r2});
}
}
}
Loop (p,0,k)
sym.push_back({j+1, vec[p]});
vlst = nlst;
}
//cout << sym.size() << '\n';
//assert(sym.size() == m);
vector<vector<int>> ans(m, vector<int>(N+1));
Loop (i,0,m) {
ans[i][0] = sym[i].first&1;
Loop (j,1,N+1) {
if (sym[i].first&1) {
int p = 0;
while (p < sym[i].second.size() && (j < sym[i].second[p].l2 || sym[i].second[p].r2 <= j))
++p;
if (p == sym[i].second.size())
continue;
auto [l1, r1, l2, r2] = sym[i].second[p];
if (j <= l1)
ans[i][j] = -2;
else if (r1-1 <= j)
ans[i][j] = -1;
else {
l2 = max(l2, l1+1);
r2 = min(r2, r1-1);
int x = (j - l2) / ((r2 - l2) / divv[sym[i].first]);
int nxt = x+1;
Loop (z,0,sym[i].first)
nxt += divv[z];
ans[i][j] = nxt;
}
} else {
int p = 0;
while (p < sym[i].second.size() && (j < sym[i].second[p].l1 || sym[i].second[p].r1 <= j))
++p;
if (p == sym[i].second.size())
continue;
auto [l1, r1, l2, r2] = sym[i].second[p];
if (j <= l2)
ans[i][j] = -1;
else if (r2-1 <= j)
ans[i][j] = -2;
else {
l1 = max(l1, l2+1);
r1 = min(r1, r2-1);
int x = (j - l1) / ((r1 - l1) / divv[sym[i].first]);
int nxt = x+1;
Loop (z,0,sym[i].first)
nxt += divv[z];
ans[i][j] = nxt;
}
}
}
}
return ans;
//vector<vector<int>> ans(20, vector<int>(N+1));
//Loop (i,0,BITS) {
// int ii = 1 << (BITS-1-i);
// ans[i*3+0].push_back(0);
// ans[i*3+1].push_back(1);
// ans[i*3+2].push_back(1);
// Loop (x,1,N+1) {
// ans[i*3+0].push_back(x&ii? i*3 + 2: i*3 + 1);
// ans[i*3+1].push_back(x&ii? -1: (i+1)*3);
// ans[i*3+2].push_back(x&ii? (i+1)*3: -2);
// }
//}
//ans[BITS*3].resize(N+1);
//return ans;
}
