#define _GLIBCXX_DEBUG #include using namespace std; const int LOG = 20; vector suffix_array(const vector &A, int mx){ int N = A.size(); vector sum(mx + 1, 0); for (int i = 0; i < N; i++){ sum[A[i] + 1]++; } for (int i = 0; i < mx; i++){ sum[i + 1] += sum[i]; } vector is_s(N); is_s[N - 1] = false; for (int i = N - 2; i >= 0; i--){ is_s[i] = A[i] < A[i + 1] || A[i] == A[i + 1] && is_s[i + 1]; } vector id(N, -1); vector pos; int M = 0; for (int i = 1; i < N; i++){ if (is_s[i] && !is_s[i - 1]){ id[i] = M; pos.push_back(i); M++; } } vector sa(N); auto induce = [&](vector& lms){ sa = vector(N, -1); vector used(N, false); vector p(mx); vector p2(mx); for (int i = 0; i < mx; i++){ p[i] = sum[i + 1] - 1; p2[i] = sum[i]; } for (int i = M - 1; i >= 0; i--){ sa[p[A[lms[i]]]] = lms[i]; p[A[lms[i]]]--; used[lms[i]] = true; } sa[p2[A[N - 1]]] = N - 1; p2[A[N - 1]]++; used[N - 1] = true; for (int i = 0; i < N; i++){ if (sa[i] > 0){ if (!is_s[sa[i] - 1] && !used[sa[i] - 1]){ sa[p2[A[sa[i] - 1]]] = sa[i] - 1; p2[A[sa[i] - 1]]++; used[sa[i] - 1] = true; } } } for (int i = 0; i < N; i++){ if (sa[i] != -1){ if (id[sa[i]] != -1){ used[sa[i]] = false; sa[i] = -1; } } } for (int i = 0; i < mx; i++){ p[i] = sum[i + 1] - 1; } for (int i = N - 1; i >= 0; i--){ if (sa[i] > 0){ if (is_s[sa[i] - 1] && !used[sa[i] - 1]){ sa[p[A[sa[i] - 1]]] = sa[i] - 1; p[A[sa[i] - 1]]--; used[sa[i] - 1] = true; } } } }; induce(pos); if (M == 0){ return sa; } vector lms; for (int i = 0; i < N; i++){ if (id[sa[i]] != -1){ lms.push_back(sa[i]); } } vector c(M); c[0] = 0; for (int i = 0; i < M - 1; i++){ c[i + 1] = c[i]; int x = lms[i]; int y = lms[i + 1]; bool ok = true; while (x < N && y < N){ if (A[x] != A[y]){ ok = false; break; } x++; y++; if (x == N || y == N){ break; } if (id[x] != -1){ if (id[y] == -1){ ok = false; } break; } } if (x == N || y == N){ ok = false; } if (!ok){ c[i + 1]++; } } vector rec(M); for (int i = 0; i < M; i++){ rec[id[lms[i]]] = c[i]; } vector sa2 = suffix_array(rec, c[M - 1] + 1); vector pos2(M); for (int i = 0; i < M; i++){ pos2[i] = pos[sa2[i]]; } induce(pos2); return sa; } vector suffix_array(const string &S){ int N = S.size(); vector A(N); for (int i = 0; i < N; i++){ A[i] = S[i]; } return suffix_array(A, 256); } template vector lcp_array(const T &A, vector &SA){ int N = A.size(); vector rank(N); for (int i = 0; i < N; i++){ rank[SA[i]] = i; } vector lcp(N - 1, 0); int h = 0; for (int i = 0; i < N; i++){ if (rank[i] > 0){ int prev = SA[rank[i] - 1]; if (h > 0){ h--; } while (i + h < N && prev + h < N){ if (A[i + h] != A[prev + h]){ break; } h++; } lcp[rank[i] - 1] = h; } } return lcp; } vector cartesian_tree_min(vector &A){ int N = A.size(); vector pr(N, -1); stack st; st.push(0); for (int i = 1; i < N; i++){ int prev = -1; while (!st.empty()){ int j = st.top(); if (A[i] < A[j]){ st.pop(); if (prev != -1){ pr[prev] = j; } prev = j; } else { break; } } if (prev != -1){ pr[prev] = i; } st.push(i); } while (st.size() >= 2){ int x = st.top(); st.pop(); pr[x] = st.top(); } return pr; } int main(){ int N, Q; cin >> N >> Q; string S; cin >> S; if (N == 1){ for (int i = 0; i < Q; i++){ cout << 0 << endl; } } else { vector SA = suffix_array(S); vector LCP = lcp_array(S, SA); vector p = cartesian_tree_min(LCP); vector L(N - 1, -1), R(N - 1, -1); int root; for (int i = 0; i < N - 1; i++){ if (p[i] == -1){ root = i; } else { if (i < p[i]){ L[p[i]] = i; } if (i > p[i]){ R[p[i]] = i; } } } int V = N * 2 - 1; p.resize(V); L.resize(V, -1); R.resize(V, -1); int cnt = 0; auto dfs = [&](auto dfs, int v) -> void { if (L[v] == -1){ L[v] = N - 1 + SA[cnt]; p[N - 1 + SA[cnt]] = v; cnt++; } else { dfs(dfs, L[v]); } if (R[v] == -1){ R[v] = N - 1 + SA[cnt]; p[N - 1 + SA[cnt]] = v; cnt++; } else { dfs(dfs, R[v]); } }; dfs(dfs, root); vector mn(V), mx(V); for (int i = 0; i < N * 2 - 1; i++){ if (i == root){ mn[i] = 1; } else { mn[i] = LCP[p[i]] + 1; } if (i < N - 1){ mx[i] = LCP[i] + 1; } else { mx[i] = N - (i - (N - 1)) + 1; } } vector dp1(V, 0); auto dfs1 = [&](auto dfs1, int v) -> void { if (v >= N - 1){ dp1[v] = 1; } if (L[v] != -1){ dfs1(dfs1, L[v]); dp1[v] += dp1[L[v]]; } if (R[v] != -1){ dfs1(dfs1, R[v]); dp1[v] += dp1[R[v]]; } }; dfs1(dfs1, root); long long curr = 0; vector dp2(V, 0); auto dfs2 = [&](auto dfs2, int v) -> void { dp2[v] = curr; curr += (long long) dp1[v] * (mx[v] - mn[v]); if (L[v] != -1){ dfs2(dfs2, L[v]); } if (R[v] != -1){ dfs2(dfs2, R[v]); } }; dfs2(dfs2, root); vector> pp(LOG, vector(V, -1)); pp[0] = p; for (int i = 0; i < LOG - 1; i++){ for (int j = 0; j < V; j++){ if (pp[i][j] != -1){ pp[i + 1][j] = pp[i][pp[i][j]]; } } } for (int i = 0; i < Q; i++){ int l, r; cin >> l >> r; l--; int v = N - 1 + l; for (int j = LOG - 1; j >= 0; j--){ if (pp[j][v] != -1){ if (mx[pp[j][v]] > r - l){ v = pp[j][v]; } } } cout << dp2[v] + (long long) dp1[v] * (r - l - mn[v]) << endl; } } }