import sys from math import log2, floor def main(): sys.setrecursionlimit(1 << 25) N, Q = map(int, sys.stdin.readline().split()) S = sys.stdin.readline().strip() queries = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)] # Suffix Array Construction sa = list(range(N)) sa.sort(key=lambda i: S[i:]) rank = [0] * N for i in range(N): rank[sa[i]] = i k = 1 tmp = [0] * N while k <= N: sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < N else -1)) tmp[sa[0]] = 0 for i in range(1, N): tmp[sa[i]] = tmp[sa[i-1]] if (rank[sa[i]] != rank[sa[i-1]] or (sa[i]+k < N and sa[i-1]+k < N and rank[sa[i]+k] != rank[sa[i-1]+k]) or (sa[i]+k >= N and sa[i-1]+k < N) or (sa[i]+k < N and sa[i-1]+k >= N)): tmp[sa[i]] += 1 rank, tmp = tmp, rank k <<= 1 # LCP Array Construction using Kasai's algorithm lcp = [0] * N h = 0 for i in range(N): if rank[i] == 0: continue j = sa[rank[i] - 1] while j + h < N and i + h < N and S[j+h] == S[i+h]: h += 1 lcp[rank[i]] = h if h > 0: h -= 1 # Sparse Table for LCP array LOG = floor(log2(N)) + 1 if N > 0 else 0 st = [[0] * N for _ in range(LOG)] st[0] = lcp[:] for k in range(1, LOG): for i in range(N - (1 << k) + 1): st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k-1))]) log_table = [0] * (N + 1) for i in range(2, N + 1): log_table[i] = log_table[i // 2] + 1 def get_lcp(l, r): if l == r: return N - sa[l] if l > r: l, r = r, l k = log_table[r - l] return min(st[k][l+1], st[k][r - (1 << k) + 1]) def compute_lcp(i, j): if i == j: return N - i ri = rank[i] rj = rank[j] return get_lcp(ri, rj) for L, R in queries: L -= 1 R -= 1 len_T = R - L + 1 K = len_T - 1 total = 0 # Part B: sum of min(lcp(i, L), K) # Part A: sum of (N - i - l + 1) where l = lcp(i, L) < len_T and S[i + l] < S[L + l] partB = 0 partA = 0 # Precompute all lcp(i, L) lcp_i_list = [] for i in range(N): l = compute_lcp(i, L) lcp_i = min(l, K) partB += lcp_i if l < len_T and i + l < N and L + l <= R and S[i + l] < S[L + l]: partA += (N - (i + l)) total = partB + partA print(total) if __name__ == "__main__": main()