#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Range{
int l, r, x;
Range(){}
Range(int _l, int _r, int _x): l(_l), r(_r), x(_x) {}
bool operator<(const Range &R) const{return l < R.l;}
};
int n, dp[5050], nxt[5050], nX[5050];
vector<int> L, X;
vector<Range> V[33];
void calc_optimal(int n){
for (int i=3;i<=n;i++){
dp[i] = 1e9;
for (int j=1;j<=min(i-2, 20);j++){
int tmp = (i-3) / j + 1;
if (dp[i] > dp[tmp] + j){
dp[i] = dp[tmp] + j;
nxt[i] = tmp;
nX[i] = j;
}
}
}
while(n>=3){
L.push_back(n);
X.push_back(nX[n]);
n = nxt[n];
}
/*for (auto &x:L) printf("%d ", x);
printf("\n");
for (auto &x:X) printf("%d ", x);
printf("\n");*/
//exit(0);
}
std::vector<std::vector<int>> devise_strategy(int N) {
n = N;
calc_optimal(n);
int ans[2] = {-1, -2};
vector<vector<int>> ret;
V[0].emplace_back(1, n, 0);
V[1].emplace_back(1, n, 0);
int s = 0;
for (int step=0;step<=(int)L.size();step++){
int px = step==0?1:X[step-1];
int cx = step==(int)L.size()?1:X[step], typ = step&1;
for (int i=s;i<s+px;i++){
//printf("YES %d\n", i);
ret.emplace_back(n+1);
ret[i][0] = typ;
int pt = 0;
for (auto &[l, r, x]:V[step]){
ret[i][l] = ans[typ];
ret[i][r] = ans[typ^1];
int cnt = 0;
while(pt<(int)V[step+1].size() && V[step+1][pt].l>=l && V[step+1][pt].r<=r){
if (V[step+1][pt].x!=i) {pt++; continue;}
cnt++;
int ll = V[step+1][pt].l, rr = V[step+1][pt].r;
//printf(" %d %d\n", ll, rr);
for (int j=l;j<=ll;j++) ret[i][j] = ans[typ];
for (int j=rr;j<=r;j++) ret[i][j] = ans[typ^1];
if (rr-ll+1 <= 2) {pt++; continue;}
int cd = (rr-ll-2) / cx + 1, pos = ll+1;
for (int t=0;t<cx;t++){
V[step+2].emplace_back(pos, min(pos+cd-1, rr-1), s+px+t);
for (int j=V[step+2].back().l;j<=V[step+2].back().r;j++) ret[i][j] = V[step+2].back().x;
pos += cd;
if (pos>=rr) break;
}
pt++;
}
assert(cnt<=1);
}
}
sort(V[step+2].begin(), V[step+2].end());
s += px;
}
//for (auto &v:ret) {for (auto &x:v){if (x>=0) printf("%d ", x); else printf("%c ", x==-1?'A':'B');} printf("\n");}
//exit(0);
return ret;
}
