不清楚到底是 $\tt RE$ 的原因还是什么，在洛谷上过了，但是交到 LOJ 上对于后 $60\%$ 的数据无法通过，全部是 $\color{red}{{\tt WA}}$ /kk，初步估计可能是主席树的问题，但是不排除因为某些 $\color{purple}{{\tt RE}}$ 的原因影响到主席树，有没有大佬帮这位刚刚学 OI 的蒟蒻康康吧/kk

#include<cstdio>
#include<algorithm>
using namespace std;

#define Endl putchar('\n')

typedef long long ll;
template<class T>inline T readin(T x){
	x=0; int f=0; char c;
	while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
	for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
	return f? -x: x;
}

const int maxn=1e5;
const int logmaxn=17;
const int inf=(1<<30)-1;

int n, m;
char s[maxn+5];

inline void input(){
	n=readin(1), m=readin(1);
	scanf("%s", s+1);
}

namespace segment_tre{
	int rt[maxn+5], cnt[maxn*logmaxn+5];
	int ls[maxn*logmaxn+5], rs[maxn*logmaxn+5];
	int ncnt=0;
	#define mid ((l+r)>>1)
	#define _lq ls[i], l, mid
	#define _rq rs[i], mid+1, r
	inline int copy(const int i){
		++ncnt;
		ls[ncnt]=ls[i], rs[ncnt]=rs[i];
		cnt[ncnt]=cnt[i];
		return ncnt;
	}
	void insert(const int pre, const int p, int& i, const int l, const int r){
		i=copy(pre); ++cnt[i];
		if(l==r) return;
		if(p<=mid) return insert(ls[pre], p, ls[i], l, mid);
		else return insert(rs[pre], p, rs[i], mid+1, r);
	}
	// 询问区间 [L, R] 中有没有点 
	int query(const int r1, const int r2, const int L, const int R, const int l, const int r){
		if(cnt[r2]-cnt[r1]==0) return 0;
		if(L<=l && r<=R) return 1;
		int ret=0;
		if(L<=mid) ret|=query(ls[r1], ls[r2], L, R, l, mid);
		if(mid<R) ret|=query(rs[r1], rs[r2], L, R, mid+1, r);
		return ret;
	}
	inline void insert(const int x, const int val){
		insert(rt[x-1], val, rt[x], 1, n);
	}
	inline int query(const int a, const int b, const int l, const int r){
//		printf("seg::query :> a == %d, b == %d, l == %d, r == %d\n", a, b, l, r);
		return query(rt[a-1], rt[b], l, r, 1, n);
	}
	#undef ls
	#undef rs
	#undef mid
	#undef _lq
	#undef _rq
}
namespace SA{
	int sa[maxn+5], c[maxn+5];
	int x[maxn*2+5], y[maxn*2+5];
	int ccnt;
	inline void getsa(){
		ccnt='z';
		for(int i=1; i<=n; ++i) ++c[x[i]=s[i]];
		for(int i=1; i<=ccnt; ++i) c[i]+=c[i-1];
		for(int i=n; i>=1; --i) sa[c[x[i]]--]=i;
		for(int k=1; k<=n; k<<=1){
			int sz=0;
			for(int i=n-k+1; i<=n; ++i) y[++sz]=i;
			for(int i=1; i<=n; ++i) if(sa[i]>k)
				y[++sz]=sa[i]-k;
			for(int i=0; i<=ccnt; ++i) c[i]=0;
			for(int i=1; i<=n; ++i) ++c[x[i]];
			for(int i=1; i<=ccnt; ++i) c[i]+=c[i-1];
			for(int i=n; i>=1; --i)
				sa[c[x[y[i]]]--]=y[i], y[i]=0;
			swap(x, y); // 注意 y 的含义发生改变 
			x[sa[1]]=1; int level=1;
			for(int i=2; i<=n; ++i)
				x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])? level: ++level;
			if(level==n) break;
			ccnt=level;
		}
	}
	int heit[maxn+5], rk[maxn+5];
	inline void getheit(){
		int h=0;
		for(int i=1; i<=n; ++i) rk[sa[i]]=i;
		for(int i=1; i<=n; ++i){
			if(rk[i]==1)continue;
			if(h) --h;
			int j=sa[rk[i]-1];
			while(i+h<=n && j+h<=n && s[i+h]==s[j+h]) ++h;
			heit[rk[i]]=h;
		}
	}
	int st[maxn+5][logmaxn+5];
	int lgg[maxn+5];
	inline void buildst(){
		lgg[0]=-1;
		for(int i=1; i<=n; ++i) lgg[i]=lgg[i>>1]+1;
		for(int i=1; i<=n; ++i) st[i][0]=heit[i];
		for(int j=1; j<=logmaxn; ++j){
			for(int i=1; i<=n-(1<<(j-1)); ++i)
				st[i][j]=min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
		}
	}
	inline int query(const int l,const int r){
//		printf("st::query :> l == %d, r == %d\n", l, r);
		if(l>r) return inf;
		int x=lgg[r-l+1];
//		printf("return %d\n", min(st[l][x], st[r-(1<<x)+1][x]));
		return min(st[l][x], st[r-(1<<x)+1][x]);
	}
	inline void check(){
		puts("<---------------- SA checker ---------------->");
		printf("this is sa:\n");
		for(int i=1; i<=n; ++i) printf("%d ", sa[i]);
		Endl;
		printf("this is rk:\n");
		for(int i=1; i<=n; ++i) printf("%d ", rk[i]);
		Endl;
		printf("this is heit:\n");
		for(int i=1; i<=n; ++i) printf("%d ", heit[i]);
		Endl;
		puts("<---------------- SA checker END ---------------->");
	}
}
inline void buildtre(){
	for(int i=1; i<=n; ++i)
		segment_tre::insert(i, SA::rk[i]);
}

int a, b, c, d;
inline int exist(const int L){
//	printf("exist :> L == %d\n", L);
	int x=SA::rk[c], up=x, down=x;
//	printf("x == %d\n", x);
	int l, r, mid;
	l=1, r=x;
	while(l<=r){
		mid=(l+r)>>1;
		if(SA::query(mid+1, x)>=L) down=mid, r=mid-1;
		else l=mid+1;
	}
	l=x, r=n;
	while(l<=r){
		mid=(l+r)>>1;
		if(SA::query(x+1, mid)>=L) up=mid, l=mid+1;
		else r=mid-1;
	}
//	printf("When L == %d, [%d, %d]\n", L, down, up);
	return segment_tre::query(a, b-L+1, down, up)>0;
}

inline void getquery(){
	int l, r, mid, ans;
	while(m--){
		a=readin(1), b=readin(1), c=readin(1), d=readin(1);
		l=1, r=min(b-a+1, d-c+1), ans=0;
		while(l<=r){
			mid=(l+r)>>1;
			printf("the first bisearch:> l == %d, r == %d, mid == %d\n", l, r, mid);
			if(exist(mid)) ans=mid, l=mid+1;
			else r=mid-1;
		}
		printf("%d\n", ans);
	}
}

signed main(){
	input();
	SA::getsa();
	SA::getheit();
//	SA::check();
	SA::buildst();
	buildtre();
	getquery();
	return 0;
}