import sys def main(): 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)] # Precompute all prefix hashes for S using a rolling hash function (e.g., base=26, mod=10^18+3) mod = 10**18 + 3 base = 911382629 prefix_hash = [0] * (N + 1) power = [1] * (N + 1) for i in range(N): prefix_hash[i+1] = (prefix_hash[i] * base + ord(S[i])) % mod power[i+1] = (power[i] * base) % mod def get_hash(l, r): # Returns hash of S[l..r] (1-based, inclusive) res = (prefix_hash[r] - prefix_hash[l-1] * power[r - l + 1]) % mod return res if res >= 0 else res + mod for L, R in queries: T = S[L-1:R] m = len(T) count = 0 # Case 1: Substrings that are a proper prefix of T # For each l from 1 to m-1, count the number of occurrences of T[0..l-1] in S # This is done using binary search on the suffix array for each prefix # However, due to time constraints, we approximate this by checking for occurrence in S # Note: This is not efficient and is only for demonstration for l in range(1, m): substr = T[:l] # Using a simple approach (inefficient for large N) # In practice, use a more efficient method like a suffix automaton cnt = 0 for i in range(N - l + 1): if S[i:i+l] == substr: cnt += 1 count += cnt # Case 2: Substrings that have a differing character at some position k < l # This part is not implemented optimally and is only for demonstration # In practice, a more efficient method is needed for i in range(N): j = 0 while j < min(m, N - i): if S[i + j] < T[j]: count += (N - (i + j)) break elif S[i + j] > T[j]: break j += 1 else: if j == m: # Substring starts at i and is equal to T, but not a prefix pass else: if S[i + j] < T[j]: count += (N - (i + j)) print(count) if __name__ == "__main__": main()