#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef long double LDB;
const int kMaxN = 1e5 + 10;
struct state {
  int len, link;
  unordered_map<char, int> next;
};
int n, m;
char str[kMaxN];
state st[kMaxN * 2];
int sz, last;
int prefix_node_id[kMaxN];
int root_of_node[kMaxN * 2];
struct SegNodeType {
  int lc, rc, sum;
};
SegNodeType seg[kMaxN * 60];
int seg_node_tot = 0;
list<int> G[kMaxN * 2];
int max_depth, fast_jump[kMaxN * 2][20];
void sam_init() {
  st[0].len = 0;
  st[0].link = -1;
  sz++;
  last = 0;
}
void sam_extend(char c) {
  int cur = sz++;
  st[cur].len = st[last].len + 1;
  int p = last;
  while (p != -1 && !st[p].next.count(c)) {
    st[p].next[c] = cur;
    p = st[p].link;
  }
  if (p == -1) {
    st[cur].link = 0;
  } else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len) {
      st[cur].link = q;
    } else {
      int clone = sz++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      while (p != -1 && st[p].next[c] == q) {
        st[p].next[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}
void InsertBasicEndPos(int &rt, int L, int R, int pos) {
  if (rt == 0) rt = ++seg_node_tot;
  seg[rt].sum++;
  if (L == R) return;
  int M = (L + R) >> 1;
  if (pos <= M)
    InsertBasicEndPos(seg[rt].lc, L, M, pos);
  else
    InsertBasicEndPos(seg[rt].rc, M + 1, R, pos);
}
int Query(int rt, int L, int R, int ql, int qr) {
  if (ql <= L && R <= qr) return seg[rt].sum;
  int M = (L + R) >> 1;
  int res = 0;
  if (ql <= M) res += Query(seg[rt].lc, L, M, ql, qr);
  if (qr >= M + 1) res += Query(seg[rt].rc, M + 1, R, ql, qr);
  return res;
}
int MergeSeg(int p, int q, int L, int R) {
  if (p == 0 || q == 0) return p + q;
  int cur = ++seg_node_tot;
  seg[cur].sum = seg[p].sum + seg[q].sum;
  if (L < R) {
    int M = (L + R) >> 1;
    seg[cur].lc = MergeSeg(seg[p].lc, seg[q].lc, L, M);
    seg[cur].rc = MergeSeg(seg[p].rc, seg[q].rc, M + 1, R);
  }
  return cur;
}
void Dfs(int nd) {
  for (int p = 1; p <= max_depth; p++) {
    if (fast_jump[nd][p - 1] == -1)
      fast_jump[nd][p] = -1;
    else
      fast_jump[nd][p] = fast_jump[fast_jump[nd][p - 1]][p - 1];
  }
  for (auto v : G[nd]) {
    fast_jump[v][0] = nd;
    Dfs(v);
    root_of_node[nd] = MergeSeg(root_of_node[nd], root_of_node[v], 1, n);
  }
}
bool IsValid(int len, int a, int b, int c, int d) {
  int cur = prefix_node_id[c + len - 1];
  for (int p = max_depth; p >= 0; p--) {
    if (fast_jump[cur][p] != -1 && st[fast_jump[cur][p]].len >= len)
      cur = fast_jump[cur][p];
  }
  return Query(root_of_node[cur], 1, n, a + len - 1, b) > 0;
}
int main() {
#ifdef local
  freopen("pro.in", "r", stdin);
#endif
  scanf("%d%d", &n, &m);
  scanf("%s", str + 1);
  sam_init();
  for (int i = 1; i <= n; i++) {
    sam_extend(str[i]);
    prefix_node_id[i] = last;
    InsertBasicEndPos(root_of_node[last], 1, n, i);
  }
  for (int i = 1; i < sz; i++) G[st[i].link].push_back(i);
  max_depth = log2(sz + 1) + 1;
  memset(fast_jump, -1, sizeof(fast_jump));
  Dfs(0);
  while (m-- > 0) {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    int L = 0, R = min(b - a + 1, d - c + 1), M, res = 0;
    while (L <= R) {
      M = (L + R) >> 1;
      if (IsValid(M, a, b, c, d)) {
        res = M;
        L = M + 1;
      } else
        R = M - 1;
    }
    printf("%d\n", res);
  }
  return 0;
}