#include <bits/stdc++.h>

 typedef long long LL;

 const int N = , M = ;

 struct Edge {

     int nex, v;

 }edge[N]; int tp;

 int tr[N][], fail[N], len[N], rt[N], last = , tot = ;

 int ls[M], rs[M], cnt, e[N], ed[N], fa[N][], pw[N];

 LL sum0[M], sum2[M], sumd[M], large[M], small[M];

 int n, q;

 char str[N];

 inline void add(int x, int y) {

     tp++;

     edge[tp].v = y;

     edge[tp].nex = e[x];

     e[x] = tp;

     return;

 }

 inline void pushup(int o) {

     if(!ls[o] && !rs[o]) return;

     sum0[o] = sum0[ls[o]] + sum0[rs[o]];

     sum2[o] = sum2[ls[o]] + sum2[rs[o]];

     sumd[o] = sumd[ls[o]] + sumd[rs[o]];

     if(ls[o] && rs[o]) sumd[o] += small[rs[o]] * large[ls[o]];

     large[o] = std::max(large[ls[o]], large[rs[o]]);

     small[o] = std::min(small[ls[o]], small[rs[o]]);

     return;

 }

 int merge(int x, int y) {

     if(!x || !y) return x | y;

     int o = ++cnt;

     large[o] = large[x];

     small[o] = small[x];

     sum0[o] = sum0[x];

     sum2[o] = sum2[x];

     sumd[o] = sumd[x];

     ls[o] = merge(ls[x], ls[y]);

     rs[o] = merge(rs[x] ,rs[y]);

     pushup(o);

     return o;

 }

 void insert(int p, int l, int r, int &o) {

     if(!o) o = ++cnt;

     if(l == r) {

         large[o] = small[o] = r;

         sum0[o] = ;

         sum2[o] = 1ll * r * r;

         sumd[o] = ;

         return;

     }

     int mid = (l + r) >> ;

     if(p <= mid) insert(p, l, mid, ls[o]);

     else insert(p, mid + , r, rs[o]);

     pushup(o);

     return;

 }

 inline void insert(char c, int id) {

     int f = c - '', p = last, np = ++tot;

     last = np;

     insert(id, , n, rt[np]);

     len[np] = len[p] + ;

     while(p && !tr[p][f]) {

         tr[p][f] = np;

         p = fail[p];

     }

     if(!p) {

         fail[np] = ;

     }

     else {

         int Q = tr[p][f];

         if(len[Q] == len[p] + ) {

             fail[np] = Q;

         }

         else {

             int nQ = ++tot;

             len[nQ] = len[p] + ;

             fail[nQ] = fail[Q];

             fail[Q] = fail[np] = nQ;

             memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));

             while(tr[p][f] == Q) {

                 tr[p][f] = nQ;

                 p = fail[p];

             }

         }

     }

     return;

 }

 int ask0(int L, int R, int l, int r, int o) {

     if(!o) return ;

     if(L <= l && r <= R) return sum0[o];

     int mid = (l + r) >> , ans = ;

     if(L <= mid) ans += ask0(L, R, l, mid, ls[o]);

     if(mid < R) ans += ask0(L, R, mid + , r, rs[o]);

     return ans;

 }

 LL ask2(int L, int R, int l, int r, int o) {

     if(!o) return ;

     if(L <= l && r <= R) return sum2[o];

     int mid = (l + r) >> ;

     LL ans = ;

     if(L <= mid) ans += ask2(L, R, l, mid, ls[o]);

     if(mid < R) ans += ask2(L, R, mid + , r, rs[o]);

     return ans;

 }

 LL askd(int L, int R, int l, int r, int o) {

     if(!o) return ;

     if(L <= l && r <= R) return sumd[o];

     int mid = (l + r) >> ;

     if(R <= mid) return askd(L, R, l, mid, ls[o]);

     if(mid < L) return askd(L, R, mid + , r, rs[o]);

     LL ans = askd(L, R, l, mid, ls[o]) + askd(L, R, mid + , r, rs[o]);

     if(ls[o] && rs[o]) {

         ans += large[ls[o]] * small[rs[o]];

     }

     return ans;

 }

 int getKpos(int k, int l, int r, int o) {

     if(l == r) return r;

     int mid = (l + r) >> ;

     if(k <= sum0[ls[o]]) return getKpos(k, l, mid, ls[o]);

     else return getKpos(k - sum0[ls[o]], mid + , r, rs[o]);

 }

 void DFS(int x) {

     for(int i = e[x]; i; i = edge[i].nex) {

         int y = edge[i].v;

         fa[y][] = x;

         DFS(y);

         rt[x] = merge(rt[x], rt[y]);

     }

     return;

 }

 inline void prework() {

     for(int i = ; i <= tot; i++) pw[i] = pw[i >> ] + ;

     for(int j = ; j <= pw[tot]; j++) {

         for(int i = ; i <= tot; i++) {

             fa[i][j] = fa[fa[i][j - ]][j - ];

         }

     }

     return;

 }

 inline int getPos(int x, int Len) {

     int t = pw[tot];

     while(t >=  && len[fa[x][]] >= Len) {

         if(len[fa[x][t]] >= Len) {

             x = fa[x][t];

         }

         t--;

     }

     return x;

 }

 inline LL getAns(int Len, int root) {

     if(Len == ) return ;

     int r1 = small[root], rn = large[root];

     int l1 = r1 - Len + , ln = rn - Len + ;

     if(ask0(r1 + Len - , ln, , n, root)) {

         return ;

     }

     LL ans = ;

     if(r1 > ln) { /// cross

         ans = sum2[root] - sumd[root] - 1ll * r1 * rn;

         LL temp = (r1 - ln);

         ans += (temp - ) * temp /  + temp * (n - temp - );

     }

     else {

         int ql = ask0(, r1 + Len - , , n, root), qr = ask0(, ln, , n, root);

         int L = qr, R = ql;

         int rL = getKpos(L, , n, root), rR = getKpos(R, , n, root), nexr = getKpos(R + , , n, root);

         ans = 1ll * (r1 - rR + Len - ) * (nexr - ln) + 1ll * rL * ln - 1ll * rR * ln;

         ans += ask2(rL + , rR, , n, root) - askd(rL, rR, , n, root);

     }

     return ans;

 }

 int main() {

     memset(small, 0x3f, sizeof(small));

     scanf("%d%d", &n, &q);

     scanf("%s", str + );

     for(int i = ; i <= n; i++) {

         insert(str[i], i);

     }

     int p = ;

     for(int i = ; i <= n; i++) {

         int f = str[i] - '';

         p = tr[p][f];

         ed[i] = p;

         //printf("i = %d p = %d \n", i, p);

     }

     for(int i = ; i <= tot; i++) add(fail[i], i);

     DFS();

     prework();

     LL SUM = 1ll * (n - ) * (n - ) / ;

     for(int i = , l, r; i <= q; i++) {

         scanf("%d%d", &l, &r);

         LL t = getAns(r - l + , rt[getPos(ed[r], r - l + )]);

         printf("%lld\n", SUM - t);

     }

     return ;

 }