#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=5105, kx=21;
int di[]={3, 3, 3, 3, 3, 3, 2}, cnt, qs[kx];
vector<vector<int>> ans(kx, vector<int> (nx+1));
vector<pair<int, int>> d[kx];
void solve(int l, int r, int layer, int nextlayer, int cur)
{
d[cur].push_back({l, r});
if (r==l+1) return;
l++, r--;
int dif=(r-l+1)/di[layer], x=l;
for (int i=0; i<di[layer]; i++) solve(x, x+dif-1, layer+1, nextlayer+di[layer], nextlayer+i), x=x+dif;
}
std::vector<std::vector<int>> devise_strategy(int N) {
solve(1, 5102, 0, 1, 0);
ans[0][1]=-1;
ans[0][5102]=-2;
for (int i=2; i<=5101; i++) ans[0][i]=(i-2)/1700+1;
//for (int i=0; i<10; i++) cout<<d[16][i].first<<' '<<d[16][i].second<<'\n';
//for (int i=0; i<10; i++) cout<<d[19][i].first<<' '<<d[19][i].second<<'\n';
//cout<<"debug "<<d[1][0].first<<' '<<d[1][0].second<<'\n';
for (int i=1; i<=7; i++) qs[i]=qs[i-1]+di[i-1];
for (int i=0; i<7; i++)
{
for (int j=1; j<=di[i]; j++)
{
ans[qs[i]+j][0]=1-(i%2);
for (auto x:d[qs[i]+j])
{
ans[qs[i]+j][x.first]=(i%2)?-1:-2;
ans[qs[i]+j][x.second]=(i%2)?-2:-1;
if (x.first+1==x.second) continue;
x.first++; x.second--;
int sz=(x.first-x.second+1)/di[i+1];
for (int k=x.first; k<=x.second; k++) ans[qs[i]+j][k]=(k-x.first)/sz+1+qs[i+1];
}
for (int k=1; ; k++)
{
if (ans[qs[i]+j][k]) break;
ans[qs[i]+j][k]=(i%2)?-1:-2;
}
for (int k=5102; ; k--)
{
if (ans[qs[i]+j][k]) break;
ans[qs[i]+j][k]=(i%2)?-2:-1;
}
}
}
vector<vector<int>> res(kx, vector<int> (N+1));
for (int i=0; i<kx; i++) for (int j=0; j<=N; j++) res[i][j]=ans[i][j];
return res;
}
// 5102
// {3, 3, 3, 3, 3, 3, 2}
/*
2 1701, 1702 3401, 3402 5101
*/
