#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5, M = 1e7 + 5;

int n, q;
string s;
int pos[N];

struct SegmentTree { //动态开点线段树，用于维护每个SAM结点的endpos 
	int sz;
	int rt[N], ls[M], rs[M], val[M];
	
	void new_chd(int x) {
		if (ls[x] == 0) {
			ls[x] = ++sz;
			rs[x] = ++sz;
			val[ls[x]] = val[rs[x]] = 0;
		}
	}
	void pushup(int x) {
		val[x] = val[ls[x]] + val[rs[x]];
	}
	void mdf(int x, int lx, int rx, int p, int v) { //给位置p增加v 
		if (lx + 1 == rx) {
			val[x] += v;
			return ;
		}
		int m = (lx + rx) / 2;
		new_chd(x);
		if (p < m)
			mdf(ls[x], lx, m, p, v);
		else
			mdf(rs[x], m, rx, p, v);
		pushup(x);
	}
	int qry(int x, int lx, int rx, int l, int r) {
		if (l <= lx && rx <= r)
			return val[x];
		if (l >= rx || lx >= r)	
			return 0;
		int m = (lx + rx) / 2;
		new_chd(x);
		return qry(ls[x], lx, m, l, r) + qry(rs[x], m, rx, l, r);
	}
	int mrg(int L, int R, int lx, int rx) { //把R合并到L，返回合并后的根结点 
		if (L == 0 || R == 0)
			return L + R;
		if (lx + 1 == rx) {
			val[L] += val[R]; 
			return L;
		}
		int x = ++sz, m = (lx + rx) / 2;
		ls[x] = mrg(ls[L], ls[R], lx, m);
		rs[x] = mrg(rs[L], rs[R], m, rx);
		pushup(x);
		return x;
	}
} st;
struct Node {
	int e[26] = {};
	int lnk = 0, len = 0;
};
int pw[25] = {1}, lg[N];
int fa[25][N];
struct SAM {
	int cnt, lst, sz;
	vector<Node> a;
	vector<int> e[N];
	
	SAM() {
		cnt = lst = 1;
		sz = 0;
		a = vector<Node>(2);
	}
	int cd(char ch) {
		return ch - 'a';
	}
	void add(char ch) {
		int x = cd(ch), p = lst;
		a.push_back(Node());
		a[lst = ++cnt].len = ++sz;
		while (p != 1 && a[p].e[x] == 0)
			a[p].e[x] = lst, p = a[p].lnk;
		if (p == 1 && a[p].e[x] == 0) {
			a[p].e[x] = lst;
			a[lst].lnk = p;
		}
		else {
			int q = a[p].e[x];
			if (a[q].len == a[p].len + 1)
				a[lst].lnk = q;
			else {
				int q_new = ++cnt;
				a.push_back(a[q]);
				a[q_new].len = a[p].len + 1;
				a[q].lnk = a[lst].lnk = q_new;
				while (a[p].e[x] == q)
					a[p].e[x] = q_new, p = a[p].lnk;
			}
		}
	}
	void set_edge() {
//		cout << cnt << endl;
		for (int i = 2; i <= cnt; i++) {
//			cout << i << ':' << a[i].lnk << ' ';
			e[a[i].lnk].push_back(i);
		}
	}
	void dfs(int x) {
		for (int i = 1; i <= 20; i++)
			fa[i][x] = fa[i - 1][fa[i - 1][x]];
		for (auto i: e[x]) {
			dfs(i);
			fa[0][i] = x;
			st.rt[x] = st.mrg(st.rt[x], st.rt[i], 1, n + 1);
		}
	}
} t;
bool chk(int x, int a, int b, int c, int d) { //判断x长度是否对(a,b,c,d)可行 
	int now = pos[c + x - 1]; //先取出s[1~c+x-1]的结点
	//找到最上面的结点 
	for (int i = 20; i >= 0; i--)
		if (fa[i][now] != 0 && t.a[fa[i][now]].len >= x)
			now = fa[i][now];
	//判断是否有以 [a+x-1,b]结尾的 
	return st.qry(st.rt[now], 1, n + 1, a + x - 1, b + 1) > 0;
}


int main() {
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	cin >> n >> q >> s;
	
	for (int i = 0; i < s.size(); i++) {
		t.add(s[i]);
		pos[i + 1] = t.lst;
	}
	t.set_edge();
	st.sz = t.cnt;
	for (int i = 1; i <= t.cnt; i++)
		st.rt[i] = i;
	for (int i = 0; i < s.size(); i++)
		st.mdf(st.rt[pos[i + 1]], 1, n + 1, i + 1, 1);
	t.dfs(1);
	
	for (int i = 1, a, b, c, d; i <= q; i++) {
		cin >> a >> b >> c >> d;
		int l = 0, r = min(b - a + 1, d - c + 1) + 1;
		while (r - l > 1) {
			int mid = (l + r) / 2;
//			cout << mid << ':' << chk(mid, a, b, c, d) << endl;
			if (chk(mid, a, b, c, d))
				l = mid;
			else
				r = mid;
		}
		cout << l << endl;
	}
	return 0;
}