#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e5+10;
const int maxm=2e6+10;
const int mod=20101009;
const ll base=1e8;
const ull base1=10007;
const ull base2=19260817;
const int maxxn=0x3f3f3f3f;
const int minxn=-0x3f3f3f3f;
const db inf=1e13;
const db eps=1e-9;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}
/*
二分这个最大前缀的长度x
如果长度合法的话，一定在[a,b-x+1]中有一个后缀和c的LCP长大于等于x
于是可以二分找到后缀排序后大于x的区间[l,r]
最后需要判断的是，在后缀数组的[l,r]上有没有对应字符串的[a,b-x+1]，可以用主席树维护 
*/
int n,m;
char s[maxn];
int sa[maxn],rk[maxn],oldrk[maxn<<1],id[maxn],cnt[maxn],tmp[maxn],height[maxn];
inline bool cmp(int x,int y,int l){
	return oldrk[x]==oldrk[y]&&oldrk[x+l]==oldrk[y+l];
}
inline void get_sa(){
	int w=300;
	for(int i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
	for(int i=1;i<=w;++i) cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
	for(int l=1,k=0;;l<<=1){
		k=0;
		for(int i=n;i+l>n;--i) id[++k]=i;
		for(int i=1;i<=n;++i) if(sa[i]>l) id[++k]=sa[i]-l;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;++i) ++cnt[tmp[i]=rk[id[i]]];
		for(int i=1;i<=w;++i) cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;--i) sa[cnt[tmp[i]]--]=id[i];
		k=0;
		memcpy(oldrk,rk,sizeof(rk));
		for(int i=1;i<=n;++i) rk[sa[i]]=cmp(sa[i],sa[i-1],l)?k:++k;
		if(k==n){
			for(int i=1;i<=n;++i) sa[rk[i]]=i;
			break;
		}
		w=k;
	}
	for(int i=1,k=0;i<=n;++i){
		if(k) --k;
		while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
		height[rk[i]]=k;
	}
}
struct ST{
	int f[maxn][20];
	inline void build(){
		for(int i=1;i<=n;++i) f[i][0]=height[i];
		for(int k=1;k<=18;++k){
			for(int i=1;i+(1<<k)-1<=n;++i){
				f[i][k]=min(f[i][k-1],f[i+(1<<(k-1))][k-1]);
			}
		} 
	}
	inline int query(int l,int r){
		if(l==r) return 1e5+10;
		if(l>r) swap(l,r);
		++l;
		int k=log2(r-l+1);
		return min(f[l][k],f[r-(1<<k)+1][k]);
	}
}S;
int rt[maxn];
struct SegmentTree{
	#define mid ((l+r)>>1)
	int ch[maxm][2],val[maxm],tot;
	inline void new_node(int &pos){
		ch[++tot][0]=ch[pos][0],ch[tot][1]=ch[pos][1],val[tot]=val[pos];
		pos=tot;
	}
	inline void update(int l,int r,int p,int &pos){
		new_node(pos);
		++val[pos];
		if(l==r) return;
		if(p<=mid) update(l,mid,p,ch[pos][0]);
		else update(mid+1,r,p,ch[pos][1]);
	}
	inline int query(int l,int r,int pl,int pr,int posl,int posr){
		if(pl<=l&&r<=pr) return val[posr]-val[posl];
		int res=0;
		if(pl<=mid) res+=query(l,mid,pl,pr,ch[posl][0],ch[posr][0]);
		if(pr>mid) res+=query(mid+1,r,pl,pr,ch[posl][1],ch[posr][1]);
		return res;
	}
	#undef mid
}T;
inline bool check(int a,int b,int c,int d,int x){
	int lpos,rpos;
	int l=1,r=rk[c];
	while(l<=r){
		int mid=(l+r)>>1;
		if(S.query(mid,rk[c])>=x) lpos=mid,r=mid-1;
		else l=mid+1;
	}
	l=rk[c],r=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(S.query(rk[c],mid)>=x) rpos=mid,l=mid+1;
		else r=mid-1;
	}
	return T.query(1,n,a,b-x+1,rt[lpos-1],rt[rpos]);
}
int main(){
	n=read(),m=read();
	scanf("%s",s+1);
	get_sa();
	S.build();
	for(int i=1;i<=n;++i){
		rt[i]=rt[i-1];
		T.update(1,n,sa[i],rt[i]);
	}
	while(m--){
		int a=read(),b=read(),c=read(),d=read();
		int l=0,r=min(b-a+1,d-c+1),ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(check(a,b,c,d,mid)) ans=mid,l=mid+1;
			else r=mid-1;
		} 
		printf("%d\n",ans);
	}
	return 0;
}