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.

见题面

见题面