// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 2e5 + 5, L = 18;

int n, q, loc[N];

char s[N];

struct SAM{
	int ch[10], link, len;
} t[N];

int last = 1, idx = 1;

void inline extend(int c) {
	int x = ++idx, p = last; t[x].len = t[p].len + 1;
	while (p && !t[p].ch[c]) t[p].ch[c] = x, p = t[p].link;
	if (!p) t[x].link = 1;
	else {
		int q = t[p].ch[c];
		if (t[p].len + 1 == t[q].len) t[x].link = q;
		else {
			int y = ++idx; t[y] = t[q];
			t[y].len = t[p].len + 1;
			while (p && t[p].ch[c] == q) t[p].ch[c] = y, p = t[p].link;
			t[q].link = t[x].link = y;
		}
	}
	last = x;
}

vector<int> g[N];

int fa[N][L], d[N], pos[N];



LL inline get(LL l, LL r) {
	return (l + r) * (r - l + 1) / 2;
}

struct Node{
	int pr, sf, l, r;
	LL v;
};

Node operator + (const Node &a, const Node &b) {
	Node c;
	c.l = a.l, c.r = b.r;
	c.pr = a.pr;
	if (!c.pr) c.pr = b.pr;
	c.sf = b.sf;
	if (!c.sf) c.sf = a.sf;
	c.v = a.v + b.v;
	if (a.sf) {
		if (b.pr) c.v += 1ll * (b.pr - b.l) * a.sf;
		else c.v += 1ll * (b.r - b.l + 1) * a.sf;
	}
	return c;
}

int rt[N];

namespace Seg{

	
	
	#define ls t[p].l
	#define rs t[p].r
	
	struct T{
		int l, r;
		Node v;
	} t[N * 19];
	
	int idx = 0;
	
	void inline pushup(int p, int l, int mid, int r) {
		if (!ls) t[p].v = (Node) { 0, 0, l, mid, 0 } + t[rs].v;
		else if (!rs) t[p].v = t[ls].v + (Node) { 0, 0, mid + 1, r, 0 };
		else t[p].v = t[ls].v + t[rs].v;
	}
	
	void ins(int &p, int l, int r, int x) {
		if (!p) p = ++idx;
		if (l == r) {
			t[p].v = (Node) { r, r, r, r, r };
			return;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) ins(ls, l, mid, x);
		else ins(rs, mid + 1, r, x);
		pushup(p, l, mid, r);
	}
	
	Node query(int p, int l, int r, int x, int y) {
		if (!p && x <= l && r <= y) return (Node) { 0, 0, l, r, 0 }; 
		if (x <= l && r <= y) return t[p].v;
		int mid = (l + r) >> 1;
		if (y <= mid) return query(ls, l, mid, x, y);
		if (x > mid) return query(rs, mid + 1, r, x, y);
		return query(ls, l, mid, x, y) + query(rs, mid + 1, r, x, y);
	}
	
	void merge(int &p, int q, int l, int r) {
		if (!q) return;
		if (!p) {
			p = q;
			return;
		}
		int la = p;
		t[p = ++idx] = t[la];
		int mid = (l + r) >> 1;
		merge(ls, t[q].l, l, mid);
		merge(rs, t[q].r, mid + 1, r);
		pushup(p, l, mid, r);
	}

}

void dfs(int u) {
	if (pos[u]) {
		Seg::ins(rt[u], 1, n, pos[u]);
	}
	for (int i = 1; i < L; i++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int v: g[u]) {
		fa[v][0] = u;
		d[v] = d[u] + 1;
		dfs(v);
		Seg::merge(rt[u], rt[v], 1, n);
	}
}

int inline fixPos(int p, int l) {
	for (int i = L - 1; ~i; i--) {
		if (fa[p][i] && t[fa[p][i]].len >= l)
			p = fa[p][i];
	}
	if (l <= t[fa[p][0]].len) p = fa[p][0];
	return p;
}


int now;

Node ask(int l, int r) {
	if (l > r) return Seg::t[0].v;
	return Seg::query(rt[now], 1, n, l, r);
}

LL G(int l, int r) {
	if (l > r) return 0;
	Node u = ask(l, r);
	Node a = ask(1, l - 1);
	if (u.pr) u.v += (u.pr - u.l) * a.sf;
	else u.v += (u.r - u.l + 1) * a.sf;
	return u.v;
}

LL sm;

LL inline Ask(int x, int y, int p) {
	now = p;
	int l = y - x + 1;
	Node u = ask(1, n);
	int A = u.pr, B = u.sf;
	LL ret = 0;
	if (A > B - l + 1) {
		ret += get(B - l + 1 - 1, A - 2);
	}
	int L = max(B - l + 1, A);
	int R = n - 1;
	Node v = ask(A + l - 1, n);
	if (v.pr) R = v.pr - 1;
	if (L <= R) {
		ret += (A + l - 1ll) * (R - L + 1);
		ret -= G(L, R);
	}
	return ret;
}

int main() {
	read(n), read(q);
	scanf("%s", s + 1);
	for (int i = 1; i <= n; i++) extend(s[i] - '0'), loc[i] = last, pos[last] = i;
	for (int i = 2; i <= idx; i++) g[t[i].link].pb(i);
    sm = 1ll * (n - 1) * (n - 2) / 2;
	dfs(1);
    while (q--) {
    	int x, y; read(x), read(y);
    	int l = y - x + 1;
    	int p = fixPos(loc[y], l);
    	printf("%lld\n", sm - Ask(x, y, p));
    }
	return 0;
}