Description
人的一生不仅要靠自我奋斗，还要考虑到历史的行程。
历史的行程可以抽象成一个 01 串，作为一个年纪比较大的人，你希望从历史的行程中获得一些姿势。
你发现在历史的不同时刻，不断的有相同的事情发生。比如，有两个人同时在世纪之交 11 年的时候上台，同样喜欢与洋人谈笑风生，同样提出了以「三」字开头的理论。
你发现，一件事情可以看成是这个 01 串的一个前缀，这个前缀最右边的位置就是这个事情的结束时间。
两件事情的相似度可以看成，这两个前缀的最长公共后缀长度。
现在你很好奇，在一段区间内结束的事情中最相似的两件事情的相似度是多少呢？
Input
第一行两个整数 n、m，表示串长和询问个数。
第二行长度为 n 的 01 串，表示历史的行程。
接下来 m 行，每行两个正整数 l 、r 表示询问的区间，包括端点，保证1≤l<r≤n。
Output
输出 m 行，对每个询问输出一个整数表示最大的相似度。
建出原串的SAM，则两个前缀的最长公共后缀为他们在parent树上的lca，问题转化为求区间内前缀两两lca深度的最大值。
将询问离线，按右端点从小到大排序。我们考虑每次加入一个字母，就将他们在parent树上到根节点的路径打上他们的标记。往根节点跑的过程中，若遇到了以前打的标记，则该节点为旧标记与新标记的lca。贪心可得应把标记尽量覆盖为较大的值。用树状数组来统计答案，下标为左端点，每次查询下标大于等于该询问左端点的最大深度。向根跑的过程中每一次遇到旧标记，就在树状数组上更新答案，并给该节点打上新标记。
往根节点跑的过程实际上就是LCT的access。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define LL long long
using namespace std;
const int N=1e5+;
int n,m,r,last,size,root;
int p[N],mx[N],ans[N],num[N];
int c[N*][],fa[N*],v[N*],tag[N*];
char s[N];
vector<int> q[N];
struct sam{int mx,fa,ch[];}t[N*];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int lowbit(int x){return x&(-x);}
void modify(int x,int v){x=n-x+;while(x<=n)mx[x]=max(mx[x],v),x+=lowbit(x);}
int query(int x){x=n-x+;int ans=;while(x)ans=max(ans,mx[x]),x-=lowbit(x);return ans;}
void ins(int c,int id)
{
int np=++size;num[id]=np;
t[np].mx=t[last].mx+;
int x=last;last=np;
while(x&&!t[x].ch[c])t[x].ch[c]=np,x=t[x].fa;
if(!x)t[np].fa=root;
else
{
int y=t[x].ch[c];
if(t[y].mx==t[x].mx+)t[np].fa=y;
else
{
int nq=++size;
t[nq]=t[y];t[nq].mx=t[x].mx+;
t[y].fa=t[np].fa=nq;
while(x&&t[x].ch[c]==y)t[x].ch[c]=nq,x=t[x].fa;
}
}
}
bool isroot(int x){return c[fa[x]][]!=x&&c[fa[x]][]!=x;}
void change(int x,int val){v[x]=tag[x]=val;}
void down(int x)
{
if(!tag[x])return;
if(c[x][])change(c[x][],tag[x]);
if(c[x][])change(c[x][],tag[x]);
tag[x]=;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],l,r;
if(c[y][]==x)l=;else l=;r=l^;
if(!isroot(y)){if(c[z][]==y)c[z][]=x;else c[z][]=x;}
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
}
void relax(int x){if(!isroot(x))relax(fa[x]);down(x);}
void splay(int x)
{
relax(x);
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))
{
if((c[y][]==x)^(c[z][]==y))rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x,int val)
{
int o=;
while(x)
{
splay(x);modify(v[x],t[x].mx);
c[x][]=o;o=x;x=fa[x];
}
tag[o]=v[o]=val;
}
void build(){for(int i=;i<=size;i++)fa[i]=t[i].fa;}
int main()
{
n=read();m=read();
scanf("%s",s+);
for(int i=;i<=m;i++)
{
p[i]=read();r=read();
q[r].push_back(i);
}
last=size=root=;
for(int i=;i<=n;i++)ins(s[i]-'',i);
build();
for(int i=;i<=n;i++)
{
access(num[i],i);
int sz=q[i].size();
for(int j=;j<sz;j++)
{
int x=q[i][j];
ans[x]=query(p[x]);
}
}
for(int i=;i<=m;i++)printf("%d\n",ans[i]);
return ;
}