人的一生不仅要靠自我奋斗，还要考虑到历史的行程。
历史的行程可以抽象成一个 01 串，作为一个年纪比较大的人，你希望从历史的行程中获得一些姿势。
你发现在历史的不同时刻，不断的有相同的事情发生。比如，有两个人同时在世纪之交 \(1\) 年的时候上台，同样喜欢与洋人谈笑风生，同样提出了以「三」字开头的理论。
你发现，一件事情可以看成是这个 01 串的一个前缀，这个前缀最右边的位置就是这个事情的结束时间。
两件事情的相似度可以看成，这两个前缀的最长公共后缀长度。
现在你很好奇，在一段区间内结束的事情中最相似的两件事情的相似度是多少呢？\(m\) 次询问，每次询问一段区间。
\(n,m\le 10^5\)
考虑建出 SAM，考虑在 SAM 上我们解决的是什么问题。
两个前缀的最长公共后缀是他们在 SAM 上的 lca，所以枚举 lca，然后考虑启发式合并的时候去维护。如果某个子树内存在三个数 \(x_1,x_2,x_3(x_1\le x_2\le x_3)\)就，那么只要 \(l\le x_1\le x_2\le r\)，或者 \(l\le x_2\le x_3\le r\)，就可以了。所以可以考虑把所有子树拆成若干个区间，当 \(l,r\) 包含了这个区间的话，就可以计算到这个贡献。
考虑启发式合并 set，合并的时候用 set 维护，然后一个 set 增加元素时二分出来前驱和后缀，加到一个数组里面。数组里面维护一个三元组 \((l,r,w)\) 表示包含了 \([l,r]\) 的区间能得到 \(w\) 的贡献，离线下来扫描线即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=1e9;
int tr[N<<1][2],ss[N],fil[N<<1],l[N<<1],ls=1,idx=1,n,ed[N<<1],m,hd[N<<1],nw,to[N<<1],k,e_num,ans[N],f[N];
vector<int>g[N];
char str[N];
set<int>s[N];
struct node{
int l,r,w;
int operator<(const node&n)const{
return r<n.r;
}
}a[N*40];
struct edge{
int v,nxt;
}e[N<<2];
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
}
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
void upd(int x,int y)
{
for(;x<=n;x+=x&-x)
ss[x]=max(ss[x],y);
}
int qry(int x)
{
int ret=0;
for(;x;x-=x&-x)
ret=max(ret,ss[x]);
return ret;
}
void ins(int s)
{
int k=ls,p=++idx;
l[p]=l[k]+1,f[p]=1;
ls=p;
while(k&&!tr[k][s])
tr[k][s]=p,k=fil[k];
if(!k)
fil[p]=1;
else
{
int q=tr[k][s];
if(l[q]==l[k]+1)
fil[p]=q;
else
{
int nw=++idx;
l[nw]=l[k]+1,tr[nw][0]=tr[q][0],tr[nw][1]=tr[q][1];
fil[nw]=fil[q],fil[q]=fil[p]=nw;
while(tr[k][s]==q)
tr[k][s]=nw,k=fil[k];
}
}
}
void ins(int x,int y,int w)
{
set<int>::iterator nx=s[x].lower_bound(y);
if(nx!=s[x].begin())
{
a[++k]=(node){*(--nx),y,w};
++nx;
}
if(nx!=s[x].end())
a[++k]=(node){y,*nx,w};
s[x].insert(y);
}
void sou(int x)
{
for(int i=hd[x];i;i=e[i].nxt)
{
sou(e[i].v);
if(!to[x]||s[to[e[i].v]].size()>s[to[x]].size())
to[x]=to[e[i].v];
}
if(!to[x])
to[x]=l[x];
for(int i=hd[x];i;i=e[i].nxt)
{
if(to[e[i].v]==to[x])
continue;
for(set<int>::iterator it=s[to[e[i].v]].begin();it!=s[to[e[i].v]].end();it++)
ins(to[x],*it,l[x]);
}
if(f[x])
ins(to[x],l[x],l[x]);
}
int main()
{
static int l[N],r[N];
n=read(),m=read();
scanf("%s",str+1);
for(int i=1;str[i];i++)
ins(str[i]-'0');
for(int i=1;i<=idx;i++)
add_edge(fil[i],i);
sou(1);
sort(a+1,a+k+1);
for(int i=1;i<=m;i++)
l[i]=read(),r[i]=read(),g[r[i]].push_back(i);
for(int i=1;i<=n;i++)
{
while(nw^k&&a[nw+1].r==i)
upd(n-a[nw+1].l+1,a[nw+1].w),++nw;
for(int j=0;j<g[i].size();j++)
ans[g[i][j]]=qry(n-l[g[i][j]]+1);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}