#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
namespace gtx{
//	Fast IO
	char *p1,*p2,buf[100000];
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
//	int read()
//	{
//		int x=0,f=1;
//		char ch=nc();
//		while(ch<48||ch>57)
//		{
//			if(ch=='-')
//				f=-1;
//			ch=nc();
//		}
//		while(ch>=48&&ch<=57)
//			x=x*10+ch-48,ch=nc();
//		return x*f;
//	}
	
	inline void read(int &x){
		x = 0;int h = 1;char tmp;
		do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
		while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
		x*=h;
	}
	inline void read(char &x){do{x=getchar();}while(x==' '||x=='\n'||x=='\r');}
	inline void write(char x){putchar(x);}
	inline void write(int x){
		if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
		do st[++tot]=x%10,x/=10; while(x);
		while(tot){putchar(st[tot--]+'0');}
	}
	inline void write(int x,char y){write(x);write(y);}
#define MAXN 200010
#define INF 0x3f3f3f3f
	namespace everything{
		int n,m,a[MAXN];
		char S[MAXN];
	}
	using namespace everything;
	namespace SuffArray{
		int p,q;
		int v[MAXN],rk[2][MAXN],sa[2][MAXN];
		inline void calcSA(int sa[MAXN],int rk[MAXN],int SA[MAXN],int RK[MAXN],int k){
			for(int i = 1;i<=n;i++) v[rk[sa[i]]]=i;
			// ????????????????
			for(int i = n;i;i--){
				if(sa[i]>k){
					SA[v[rk[sa[i]-k]]--] = sa[i]-k;
					// ?????????????????
				}
			}
			for(int i = n-k+1;i<=n;i++) SA[v[rk[i]]--]=i;// ???????????
			for(int i = 1;i<=n;i++){
				RK[SA[i]] = RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
			}
		}
		inline void workoutSAandRK(){
			p = 0;q = 1;
			for(int i = 1;i<=n;i++) v[a[i]]++;
			for(int i = 1;i<=256;i++) v[i] += v[i-1];
			for(int i = 1;i<=n;i++){
				sa[p][v[a[i]]--] = i;
			}
			for(int i = 1;i<=n;i++){
				rk[p][sa[p][i]] = rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]);
			}
			int k = 1;
			for(;k<n;k<<=1){
				calcSA(sa[p],rk[p],sa[q],rk[q],k);
				swap(p,q);
			}
		}
#define RK SuffArray::rk[SuffArray::p]
#define SA SuffArray::sa[SuffArray::p]
		int h[MAXN];
		inline void get_h(){
			int k = 0;
			for(int i = 1;i<=n;i++){
				if(RK[i]==1) h[RK[i]] = 0;
				else{
					int j = SA[RK[i]-1];
					while(a[j+k]==a[i+k]) k++;
					h[RK[i]] = k;if(k>0) k--;
				}
			}
		}
		inline void init(){
			workoutSAandRK();
			get_h();
		}
	}
	using namespace SuffArray;
	namespace segmen {
        namespace ZhuXiShu{
            struct segmentree{
                int l,r;
                int lson,rson;
                int sum;
            }tree[20000000];
            void pushup(int k){
                tree[k].sum = tree[tree[k].lson].sum+tree[tree[k].rson].sum;
            }
            int segmentsum;
            int build(int l,int r){
                int k = ++segmentsum;
                tree[k].l = l;
                tree[k].r = r;
                return k; 
            }
            int build(segmentree x){
                int k = ++segmentsum;
                tree[k] = x;
                return k;
            }
            int root[MAXN];
            void modify(int k,int x){
                if(tree[k].l>x||tree[k].r<x) return;
                if(tree[k].l==x&&tree[k].r==x) return tree[k].sum++,void();
                int mid = (tree[k].l+tree[k].r)>>1;
                if(tree[k].lson) tree[k].lson = build(tree[tree[k].lson]);
                else tree[k].lson = build(tree[k].l,mid);
                if(tree[k].rson) tree[k].rson = build(tree[tree[k].rson]);
                else tree[k].rson = build(mid+1,tree[k].r);
                modify(tree[k].lson,x);
                modify(tree[k].rson,x);
				pushup(k);
            }
            int rank(int lroot,int rroot,int l,int r,int x){
                auto Sum = [](int lroot,int rroot){
                    return tree[rroot].sum-tree[lroot].sum;
                };
                if(Sum(lroot,rroot)==0) return 0;
                if(r<x) return Sum(lroot,rroot);
                if(l>x) return 0;
                if(l==r) return 0;
                int mid = (l+r)>>1;
                return rank(tree[lroot].lson,tree[rroot].lson,l,mid,x)+
                       rank(tree[lroot].rson,tree[rroot].rson,mid+1,r,x);
            }
            int kth(int lroot,int rroot,int l,int r,int x){
                if(l==r) return l;
                auto Sum = [](int lroot,int rroot){
                    return tree[rroot].sum-tree[lroot].sum;
                };
                if(Sum(tree[lroot].lson,tree[rroot].lson)>=x) return kth(tree[lroot].lson,tree[rroot].lson,l,(l+r)>>1,x);
                return kth(tree[lroot].rson,tree[rroot].rson,(l+r)/2+1,r,x-Sum(tree[lroot].lson,tree[rroot].lson));
            }
            int ask_pre(int lroot,int rroot,int x){
                int Rk = rank(lroot,rroot,1,n,x+1);
                if(Rk==0) return -INF;
                return kth(lroot,rroot,1,n,Rk);
            }
            int ask_suf(int lroot,int rroot,int x){
                int Rk = rank(lroot,rroot,1,n,x);
                if(Rk==tree[rroot].sum-tree[lroot].sum) return INF;
                return kth(lroot,rroot,1,n,Rk+1);
            }
        }
		namespace GuanYuHDeXianDuanShu{
			int L[MAXN<<2],R[MAXN<<2];
			int minn[MAXN<<2];
			inline void pushup(int k){
				minn[k] = min(minn[k*2],minn[k*2+1]);
			}
			inline void build(int k,int l,int r){
				L[k] = l;
				R[k] = r;
				if(l==r){
					minn[k] = h[l];
					return;
				}
				int mid = (l+r)>>1;
				build(k*2,l,mid);
				build(k*2+1,mid+1,r);
				pushup(k);
			}
			inline int ask_minn(int k,int l,int r){
				if(L[k]>r||R[k]<l) return INF;
				if(L[k]>=l&&R[k]<=r) return minn[k];
				return min(ask_minn(k*2,l,r),ask_minn(k*2+1,l,r));
			}
		}
		using namespace ZhuXiShu;
		using namespace GuanYuHDeXianDuanShu;
	}
	using namespace segmen;
#define q everything::q
	inline int Q(int x,int y){
		if(x>y) swap(x,y);
		return ask_minn(1,x+1,y);
	}
	bool check(int a,int b,int c,int d,int mid){
		int L = a,R = b-mid;
		if(L>R) return true;
		int pre = ask_pre(root[L-1],root[R],RK[c]);
//		cout <<L << " " << R << " " << RK[c] << " " << pre <<endl;
		int suf = ask_suf(root[L-1],root[R],RK[c]);
//		cout <<L << " " << R << " "  << RK[c] << " " << suf <<endl;
		if(pre==-INF) return Q(suf,RK[c])<=mid;
		if(suf==INF) return Q(pre,RK[c])<=mid;
		return max(Q(suf,RK[c]),Q(pre,RK[c]))<=mid;
	}
	signed main(){
		read(n);read(m);
		for(int i = 1;i<=n;i++){
			read(S[i]);
			a[i] = S[i];
		}
		init();
		GuanYuHDeXianDuanShu::build(1,1,n);
        root[1] = build(1,n);
		for(int i = 1;i<=n;i++){
            if(!root[i]){
                root[i] = build(tree[root[i-1]]);
            }
            modify(root[i],RK[i]);
		}
		while(m--){
			int a,b,c,d;
			read(a);read(b);read(c);read(d);
			int l = 0,r = b-a+1,ans;
			while(l<=r){
				int mid = (l+r)>>1;
				if(check(a,b,c,d,mid)){
					r = mid-1;
					ans = mid;
				}else l = mid+1;
			}
			// if(m%1000==0) cerr << "1000 is OK!\n";
			write(min(ans,d-c+1),endl);
		}
		return 0;
	}
}
signed main(){
//	freopen("str10.in","r",stdin);
//	freopen("str10.txt","w",stdout);
//	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
//	gtx::read(T);
	while(T--) gtx::main();
	return 0;
}