How Many Substrings?

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., a to z) 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

Sample Output 0

Explanation 0

Given aabaa, we perform the following queries:

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