进食后人!!!

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+12;
const int LG=log2(N)+3;
const int M=26;
const int K=19;

struct segment_Tree{
	struct seg{
		int ls,rs;
		bool has;
	}tr[N*LG*4];
	int root[N];
	int tot=0;
	void upd(int k){
		tr[k].has=tr[tr[k].ls].has|tr[tr[k].rs].has; 
	}
	void change(int &k,int L,int R,int x,int v){
		if(!k){
			k=++tot;
		}
		if(L==R){
			tr[k].has=v;
			return; 
		}
		int mid=(L+R)>>1;
		if(x<=mid){
			change(tr[k].ls,L,mid,x,v);
		}else{
			change(tr[k].rs,mid+1,R,x,v);
		}
		upd(k);
	}
	bool quary(int k,int L,int R,int ql,int qr){
		if(!k){
			return 0;
		}
		if(ql<=L&&R<=qr){
			return tr[k].has;
		}
		int mid=(L+R)>>1;
		bool ans=0;
		if(ql<=mid){
			ans|=quary(tr[k].ls,L,mid,ql,qr);
		}
		if(qr>mid){
			ans|=quary(tr[k].rs,mid+1,R,ql,qr);
		}
		return ans;
	}
	void cpy(int k1,int k2){//copy k2 to k1
		tr[k1].ls=tr[k2].ls;
		tr[k1].rs=tr[k2].rs;
		tr[k1].has=tr[k2].has;
	}
	int Merge(int k1,int k2,int L,int R){
		if(!k1&&!k2){
			return 0;
		}
		int k=++tot;
		if(!k1||!k2){
			if(!k1){
				cpy(k,k2);
			}else{
				cpy(k,k1);
			}
			return k;
		}
		int mid=(L+R)>>1;
		tr[k].ls=Merge(tr[k1].ls,tr[k2].ls,L,mid);
		tr[k].rs=Merge(tr[k1].rs,tr[k2].rs,mid+1,R);
		upd(k);
		return k;
	}
}tr;

struct SAM{
	struct sam{
		int link;
		int son[M];
		int len;
	}tr[N*2];
	
	int id[N];
	
	int root=1,tot=1,lst=1;
	
	void init(){
		root=1,tot=lst=root;
	}
	
	int add(int x){
		tr[++tot].len=tr[x].len+1;
		return tot;
	}
	void ins(char c,int x){
		c-='a';
		int p=add(lst);
		int now=lst;
		while(now&&!tr[now].son[c]){
			tr[now].son[c]=p;
			now=tr[now].link;
		}
		if(!now){
			tr[p].link=root;
		}else{
			int t=tr[now].son[c];
			if(tr[now].len==tr[t].len+1){
				tr[p].link=t;
			}else{
				int clone=add(t);
				for(int i=0;i<M;++i){
					tr[clone].son[i]=tr[t].son[i];
				}
				tr[clone].link=tr[t].link;
				tr[clone].len=tr[now].len+1;
				while(now&&tr[now].son[c]==t){
					tr[now].son[c]=clone;
					now=tr[now].link;
				}
				tr[t].link=tr[p].link=clone;
			}
		}
		lst=p;
		id[x]=p;
	}
}sam;

int n,m;
int head[N],to[N<<1],nex[N<<1],tot=0;
inline void mkr(int u,int v){
	to[++tot]=v,nex[tot]=head[u],head[u]=tot;
}
void build_parent_tree(){
	for(int i=2;i<=sam.tot;++i){
//		cerr<<sam.tr[i].link<<"->"<<i<<endl;
		mkr(sam.tr[i].link,i);
	}
}

int fa[N][K+1];

void dfs(int now,int Fa){
	fa[now][0]=Fa;
	for(int i=1;i<=K;++i){
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for(int f=head[now];f;f=nex[f]){
		int t=to[f];
		dfs(t,now);
		tr.root[now]=tr.Merge(tr.root[now],tr.root[t],1,n);
	}
}

bool check(int mid,int a,int b,int c){
	int now=sam.id[c+mid-1];
	for(int i=K;i>=0;--i){
		if(fa[now][i]&&sam.tr[fa[now][i]].len>=mid){
			now=fa[now][i];
		}
	}
	return tr.quary(tr.root[now],1,n,a+mid-1,b);
}

char s[N];

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m;
	
	sam.init();
	
	for(int i=1;i<=n;++i){
		cin>>s[i];
		sam.ins(s[i],i);
		tr.change(tr.root[sam.id[i]],1,n,i,1);
	}
	
	build_parent_tree();
	dfs(1,0);
	
	int a,b,c,d;
	while(m--){
		cin>>a>>b>>c>>d;
		int L=0,R=min(b-a+1,d-c+1),mid,ans=0;
		while(L<=R){
			mid=(L+R)>>1;
			if(check(mid,a,b,c)){
				ans=mid;L=mid+1;
			}else{
				R=mid-1;
			}
		}
		cout<<ans<<"\n";
	}
	
	return 0;
}