namespace SA
{
static const int Sigma=127;
int rk[MAX],sa[MAX],olrk[MAX<<1],buc[MAX];
int id[MAX],pid[MAX],height[MAX];
char s[MAX]; int n;
inline void Build()
{
n=strlen(s+1);
for(int i=1;i<=n;++i) ++buc[rk[i]=s[i]];
for(int i=1;i<=Sigma;++i) buc[i]+=buc[i-1];
for(int i=n;i;--i) sa[buc[rk[i]]--]=i;
for(int w=1,m=Sigma,p=0;;w<<=1,m=p,p=0)
{
for(int i=n;i+w>n;--i) id[++p]=i;
for(int i=1;i<=n;++i) if(sa[i]>w) id[++p]=sa[i]-w;
for(int i=1;i<=m;++i) buc[i]=0;
for(int i=1;i<=n;++i) ++buc[pid[i]=rk[id[i]]];
for(int i=1;i<=m;++i) buc[i]+=buc[i-1];
for(int i=n;i;--i) sa[buc[pid[i]]--]=id[i];
p=0;
for(int i=1;i<=n;++i) olrk[i]=rk[i];
for(int i=1;i<=n;++i) p+=(olrk[sa[i]]!=olrk[sa[i-1]]||olrk[sa[i]+w]!=olrk[sa[i-1]+w]),rk[sa[i]]=p;
if(p==n) break;
}
}
inline void GetHeight()
{
for(int i=1,k=0;i<=n;++i)
{
for(k=max(k-1,0ll);s[i+k]==s[sa[rk[i]-1]+k];++k);
height[rk[i]]=k;
}
}
}