#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int> > res;
vector<int>op;
vector<int>to;
void go(int x,int l,int r,int ll,int rr,int u)
{
res[x][0]=u;
for(int i=ll;i<=l;i++)res[x][i]=-u-1;
for(int i=r;i<=rr;i++)res[x][i]=u-2;
if(r<l+2)return;
int len=r-l-1;
int ln1=(len+op[len+2]-1)/op[len+2],ln2=len/op[len+2],cn1=len%op[len+2];
int cn2=op[len+2]-cn1;
int lst=to[x];
int st=l+1;
for(int i=0;i<cn1;i++)
{
for(int j=st;j<st+ln1;j++)res[x][j]=lst;
go(lst,st,st+ln1-1,l,r,1-u);
st+=ln1;
lst++;
}
for(int i=0;i<cn2;i++)
{
for(int j=st;j<st+ln2;j++)res[x][j]=lst;
go(lst,st,st+ln1-1,l,r,1-u);
lst++;
st+=ln2;
}
}
vector<vector<int> > devise_strategy(int N)
{
int NN=N;
N=5000;
vector<int>dp(N+1),opt(N+1);
dp[1]=0;
dp[2]=0;
for(int i=3;i<=N;i++)
{
dp[i]=1000000;
for(int j=1;j<=i-2;j++)
{
int h=(i-2+j-1)/j,d=(i-2)/j,r=(i-2)%j;
int g=j-r;
int res=j+dp[h];
if(res<dp[i]){dp[i]=res;opt[i]=j;}
}
// cout<<i<<" "<<dp[i]<<endl;
}
//cout<<dp[N]<<endl;
to.clear();
vector<int>g;
g.push_back(N);
int num=1;
while(!g.empty())
{
int h=to.size()+num;
for(int i=0;i<num;i++)to.push_back(h);
vector<int>gg;
int f=0;
for(auto u:g)
{ f=max(f,opt[u]);
if(opt[u]!=0)
{gg.push_back((u-2)/opt[u]);gg.push_back(((u-2)+opt[u]-1)/opt[u]);}}
g=gg;
num=f;
}
// cout<<to.size()<<endl;
res=vector<vector<int> >(to.size(),vector<int>(N+1));
op=opt;
go(0,1,N,1,N,0);
for(int i=0;i<res.size();i++)
while(res[i].size()>NN+1)res[i].pop_back();
return res;
}
/*int main()
{
vector<vector<int> > v=devise_strategy(4993);
cout<<v.size()<<endl;
int hh=0;
for(int i=0;i<v.size();i++)
{
for(int j=0;j<v[i].size();j++)hh=max(hh,v[i][j]);//cout<<v[i][j]<<" ";
// cout<<endl;
}
cout<<hh;
return 0;
}*/
