Consider a string of $n$ characters, $\boldsymbol{\mathrm{~S~}}$, of where each character is indexed from $\mbox{0}$ to $n-1$.

You are given $\textit{q}$ queries in the form of two integer indices: ${\mbox{left}}$ and $\textit{right}$. For each query, count and print the number of different substrings of $\boldsymbol{\mathrm{~S~}}$ in the inclusive range between ${\mbox{left}}$ and $\textit{right}$. 

Note: Two substrings are different if their sequence of characters differs by at least one. For example, given the string $\boldsymbol{s}=$ aab, substrings $\boldsymbol{s}_{[0,0]}=$ a and $\boldsymbol{s}_{[1,1]}\:=\:$ a are the same but substrings $\textbf{s}_{[0,1]}\:=\:$ aa and $\boldsymbol{s}_{[1,2]}=$ ab are different.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and $\textit{q}$. 

The second line contains a single string denoting $\boldsymbol{\mathrm{~S~}}$. 

Each of the $\textit{q}$ subsequent lines contains two space-separated integers describing the respective values of ${\mbox{left}}$ and $\textit{right}$ for a query.

Constraints

$0\leq left\leq right\leq n-1$  
String $\boldsymbol{\mathrm{~S~}}$ consists of lowercase English alphabetic letters (i.e., a to z) only.

Subtasks  

For $30\%$ of the test cases, $1\leq n,q\leq100$  
For $50\%$ of the test cases, $1\leq n,q\leq3000$  
For $100\%$ of the test cases, $1\leq n,q\leq10^5$  

Output Format

For each query, print the number of different substrings in the inclusive range between index ${\mbox{left}}$ and index $\textit{right}$ on a new line. 

Sample Input 0
5 5
aabaa
1 1
1 4
1 1
1 4
0 2

Sample Output 0
1
8
1
8
5

Explanation 0

Given $\boldsymbol{s}=$ aabaa, we perform the following $q=5$ queries:

1 1: The only substring of a is itself, so we print $\mbox{1}$ on a new line.
1 4: The substrings of abaa are a, b, ab, ba, aa, aba, baa, and abaa, so we print $8$ on a new line.
1 1: The only substring of a is itself, so we print $\mbox{1}$ on a new line.
1 4: The substrings of abaa are a, b, ab, ba, aa, aba, baa, and abaa, so we print $8$ on a new line.
0 2: The substrings of aab are a, b, aa, ab, and aab, so we print $5$ on a new line.

Difficulty: HARD
Tags: String algorithms

Starter code:

Solutions:
from time import time

def kasai(s, suff, n):
	lcp = [0] * n
	inv = [0] * n
	for i in range(n):
		inv[suff[i]] = i
	k = 0
	for i in range(n):
		if inv[i] == n - 1:
			k = 0
			continue
		j = suff[inv[i] + 1]
		while i + k < n and j + k < n and (s[i + k] == s[j + k]):
			k += 1
		lcp[inv[i]] = k
		if k > 0:
			k -= 1
	return lcp
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
for _ in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	sub = s[left:right + 1]
	length = right - left + 1
	suffix = [[i, sub[i:]] for i in range(length)]
	suffix.sort(key=lambda x: x[1])
	(suff, suffix) = [list(t) for t in zip(*suffix)]
	lcp = kasai(sub, suff, length)
	count = len(suffix[0])
	for i in range(length - 1):
		count += len(suffix[i + 1]) - lcp[i]
	print(count)


def lcp(s1, s2):
	if (s1[1], s2[1]) in lcp_dict:
		return lcp_dict[s1[1], s2[1]]
	count = 0
	while len(s1[0]) > count and len(s2[0]) > count and (s1[0][count] == s2[0][count]):
		count += 1
	lcp_dict[s1[1], s2[1]] = count
	return count
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
suf = []
for i in range(len(s)):
	suf.append((s[n - i - 1:n], n - i - 1))
lcp_dict = dict()
for a0 in range(q):
	(left, right) = [int(i) for i in input().split()]
	sufq = [s for s in suf if s[1] >= left and s[1] <= right]
	sufq.sort(key=lambda s: s[0][0:right + 1 - s[1]])
	temp = sufq[0]
	count = right + 1 - temp[1]
	for i in range(1, len(sufq)):
		(temp_s, temp_i) = sufq[i]
		count += right + 1 - temp_i - min(lcp(temp, (temp_s, temp_i)), right + 1 - max(temp_i, temp[1]))
		temp = (temp_s, temp_i)
	print(count)


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


from time import time

def kasai(s, suff, n):
	lcp = [0] * n
	inv = [0] * n
	for i in range(n):
		inv[suff[i]] = i
	k = 0
	for i in range(n):
		if inv[i] == n - 1:
			k = 0
			continue
		j = suff[inv[i] + 1]
		while i + k < n and j + k < n and (s[i + k] == s[j + k]):
			k += 1
		lcp[inv[i]] = k
		if k > 0:
			k -= 1
	return lcp
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
for _ in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	sub = s[left:right + 1]
	length = right - left + 1
	suffix = [[i, sub[i:]] for i in range(length)]
	suffix.sort(key=lambda x: x[1])
	(suff, suffix) = [list(t) for t in zip(*suffix)]
	lcp = kasai(sub, suff, length)
	count = len(suffix[0])
	for i in range(length - 1):
		count += len(suffix[i + 1]) - lcp[i]
	print(count)


import os
import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import os
import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def lcp(s1, s2):
	if (s1[1], s2[1]) in lcp_dict:
		return lcp_dict[s1[1], s2[1]]
	count = 0
	while len(s1[0]) > count and len(s2[0]) > count and (s1[0][count] == s2[0][count]):
		count += 1
	lcp_dict[s1[1], s2[1]] = count
	return count
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
suf = []
for i in range(len(s)):
	suf.append((s[n - i - 1:n], n - i - 1))
lcp_dict = dict()
for a0 in range(q):
	(left, right) = [int(i) for i in input().split()]
	sufq = [s for s in suf if s[1] >= left and s[1] <= right]
	sufq.sort(key=lambda s: s[0][0:right + 1 - s[1]])
	temp = sufq[0]
	count = right + 1 - temp[1]
	for i in range(1, len(sufq)):
		(temp_s, temp_i) = sufq[i]
		count += right + 1 - temp_i - min(lcp(temp, (temp_s, temp_i)), right + 1 - max(temp_i, temp[1]))
		temp = (temp_s, temp_i)
	print(count)


def sub_string(s):
	sub = 0
	n = len(s)
	f = 0
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			sub += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			sub += f
			i += 1
	return sub
(n, q) = map(int, input().strip().split())
s = input().strip()
for a0 in range(q):
	(left, right) = map(int, input().strip().split())
	print(sub_string(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import math
import os
import random
import re
import sys
import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def lcp(s1, s2):
	if (s1[1], s2[1]) in lcp_dict:
		return lcp_dict[s1[1], s2[1]]
	count = 0
	while len(s1[0]) > count and len(s2[0]) > count and (s1[0][count] == s2[0][count]):
		count += 1
	lcp_dict[s1[1], s2[1]] = count
	return count
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
suf = []
for i in range(len(s)):
	suf.append((s[n - i - 1:n], n - i - 1))
lcp_dict = dict()
for a0 in range(q):
	(left, right) = [int(i) for i in input().split()]
	sufq = [s for s in suf if s[1] >= left and s[1] <= right]
	sufq.sort(key=lambda s: s[0][0:right + 1 - s[1]])
	temp = sufq[0]
	count = right + 1 - temp[1]
	for i in range(1, len(sufq)):
		(temp_s, temp_i) = sufq[i]
		count += right + 1 - temp_i - min(lcp(temp, (temp_s, temp_i)), right + 1 - max(temp_i, temp[1]))
		temp = (temp_s, temp_i)
	print(count)


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substring(s):
	ss = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			ss += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			ss += f
			i += 1
	return ss
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substring(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import math
import os
import random
import re
import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import math
import os
import random
import re
import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import math
import os
import random
import re
import sys

def count_str(s):
	su = 0
	n = len(s)
	f = 0
	Str = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(count_str(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def sub(s):
	m = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			m += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			m += f
			i += 1
	return m
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(sub(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def substr(a):
	b = 0
	c = len(a)
	d = 0
	f = ''
	g = 0
	while g < c:
		if a[d:g + 1] in a[0:g]:
			b += d
			g += 1
		elif g != d:
			d += 1
		else:
			d = g + 1
			b += d
			g += 1
	return b
(c, q) = input().strip().split(' ')
(c, q) = [int(c), int(q)]
a = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(a[left:right + 1]))


import sys

def star():

	def saiteja(harinatgh):
		sai = 0
		kamal = len(harinatgh)
		sayys = 0
		hama = ''
		i = 0
		while i < kamal:
			if harinatgh[sayys:i + 1] in harinatgh[0:i]:
				sai += sayys
				i += 1
			elif i != sayys:
				sayys += 1
			else:
				sayys = i + 1
				sai += sayys
				i += 1
		return sai
	(kamal, quest) = input().strip().split(' ')
	(kamal, quest) = [int(kamal), int(quest)]
	harinatgh = input().strip()
	lover = []
	for a0 in range(quest):
		(hari, krishna) = input().strip().split(' ')
		(hari, krishna) = [int(hari), int(krishna)]
		print(saiteja(harinatgh[hari:krishna + 1]))
star()


def substr(a):
	b = 0
	c = len(a)
	d = 0
	f = ''
	g = 0
	while g < c:
		if a[d:g + 1] in a[0:g]:
			b += d
			g += 1
		elif g != d:
			d += 1
		else:
			d = g + 1
			b += d
			g += 1
	return b
(c, q) = input().strip().split(' ')
(c, q) = [int(c), int(q)]
a = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(a[left:right + 1]))


import sys

def substr(s):
	sub = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			sub += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			sub += f
			i += 1
	return sub
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def substr(a):
	b = 0
	c = len(a)
	d = 0
	f = ''
	g = 0
	while g < c:
		if a[d:g + 1] in a[0:g]:
			b += d
			g += 1
		elif g != d:
			d += 1
		else:
			d = g + 1
			b += d
			g += 1
	return b
(c, q) = input().strip().split(' ')
(c, q) = [int(c), int(q)]
a = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(a[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(p, q) = input().strip().split(' ')
(p, q) = [int(p), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(O):
	su = 0
	E = len(O)
	A = 0
	T = ''
	W = 0
	while W < E:
		if O[A:W + 1] in O[0:W]:
			su += A
			W += 1
		elif W != A:
			A += 1
		else:
			A = W + 1
			su += A
			W += 1
	return su
(E, S) = input().strip().split(' ')
(E, S) = [int(E), int(S)]
O = input().strip()
l = []
for a0 in range(S):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(O[left:right + 1]))


def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def substring1(n):
	b = 0
	c = len(n)
	d = 0
	f = ''
	g = 0
	while g < c:
		if n[d:g + 1] in n[0:g]:
			b += d
			g += 1
		elif g != d:
			d += 1
		else:
			d = g + 1
			b += d
			g += 1
	return b
(c, q) = input().strip().split(' ')
(c, q) = [int(c), int(q)]
n = input().strip()
l1 = []
for n0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substring1(n[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	g = 0
	j = ''
	p = 0
	while p < n:
		if s[g:p + 1] in s[0:p]:
			su += g
			p += 1
		elif p != g:
			g += 1
		else:
			g = p + 1
			su += g
			p += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import math
import os
import random
import re
import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import math
import os
import random
import re
import sys

def substr(a):
	s = 0
	n = len(a)
	f = 0
	x = ''
	i = 0
	while i < n:
		if a[f:i + 1] in a[0:i]:
			s += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			s += f
			i += 1
	return s
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
a = input().strip()
l = []
for a0 in range(q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	print(substr(a[l:r + 1]))


import math
import os
import random
import re
import sys

def substr(s):
	sub = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			sub += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			sub += f
			i += 1
	return sub
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))


import sys

def substr(s):
	su = 0
	n = len(s)
	f = 0
	x = ''
	i = 0
	while i < n:
		if s[f:i + 1] in s[0:i]:
			su += f
			i += 1
		elif i != f:
			f += 1
		else:
			f = i + 1
			su += f
			i += 1
	return su
(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
s = input().strip()
l = []
for a0 in range(q):
	(left, right) = input().strip().split(' ')
	(left, right) = [int(left), int(right)]
	print(substr(s[left:right + 1]))