Substring Occurrence Pairs

Given a numeric string ( s ) of length ( n ) and ( q ) queries, we define ( |s| ) as the length of ( s ). For each valid index ( i ) ((1 \leq i \leq |s|)), let ( s_i ) denote the ( i)-th character of ( s ), and for any two indices ( l ) and ( r ), ( s_{l,r} ) denotes the substring formed by concatenating the characters from the ( l)-th to the ( r)-th positions (from left to right), with the convention that if ( l > r ) or if either ( l ) or ( r ) is not in the range ( [1,|s|] ), then ( s_{l,r} ) is the empty string.

For a given query, a substring ( t = s_{l,r} ) is provided. Your task is to count the number of pairs of indices ( (i, j) ) satisfying ( 1 \leq i < j \leq n ) and ( i+1 < j ) such that ( t ) appears as a substring in at least one of the following three substrings of ( s ):

1. The prefix ( s_{1,i} ) (i.e. the first ( i ) characters),
2. The middle substring ( s_{i+1,j-1} ) (i.e. the substring between the prefix and the suffix), or
3. The suffix ( s_{j,n} ) (i.e. from the ( j)-th character to the end).

Output the count for each query.

inputFormat

The input begins with a line containing two integers ( n ) and ( q ) --- the length of the string and the number of queries. The second line contains a string ( s ) made up only of digits. Each of the following ( q ) lines contains two integers ( l ) and ( r ), describing a query where the substring ( s_{l,r} ) is given.

outputFormat

For each query, output a single line containing the number of pairs ( (i, j) ) that satisfy ( 1 \leq i < j \leq n ), ( i+1 < j ), and such that the substring ( s_{l,r} ) appears in at least one of ( s_{1,i} ), ( s_{i+1,j-1} ), or ( s_{j,n} ).

sample

5 2
12345
1 2
2 4

6
5