Consider a string of characters, , of where each character is indexed from to .
You are given queries in the form of two integer indices: and . For each query, count and print the number of different substrings of in the inclusive range between and .
Note: Two substrings are different if their sequence of characters differs by at least one. For example, given the string aab, substrings a and a are the same but substrings aa and ab are different.
Input Format
The first line contains two space-separated integers describing the respective values of and .
The second line contains a single string denoting .
Each of the subsequent lines contains two space-separated integers describing the respective values of and for a query.
Constraints
- String consists of lowercase English alphabetic letters (i.e.,
atoz) only.
Subtasks
- For of the test cases,
- For of the test cases,
- For of the test cases,
Output Format
For each query, print the number of different substrings in the inclusive range between index and index 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 aabaa, we perform the following queries:
1 1: The only substring ofais itself, so we print on a new line.1 4: The substrings ofabaaarea,b,ab,ba,aa,aba,baa, andabaa, so we print on a new line.1 1: The only substring ofais itself, so we print on a new line.1 4: The substrings ofabaaarea,b,ab,ba,aa,aba,baa, andabaa, so we print on a new line.0 2: The substrings ofaabarea,b,aa,ab, andaab, so we print on a new line.