# Unique Substrings Query emrul_mu #HelpFloodVictims Program...
Limits 1s, 128 MB

You will be given a string $s$ of length $n$.

Consider substring $s[i, n]$ (where $i$ is the starting position and $n$ is the ending position) of $s$ as a string called $X_i$.

You need to perform $m$ queries on that string. A query is defined as:

L R P Q


For each query, you need to calculate:

$\sum_{i=L}^{R}{f(X_i, P, Q)}$

Where,

• $f(X_i, P, Q)$ is the number of unique substrings of $X_i$ of length between $P$ and $Q$.

## Input

The first line of the input is followed by two integers $n$ ($1 ≤ n ≤ 10^3$) and $m$ ($1 ≤ m ≤ 10^6$).

The second line contains the string $s$ of only lowercase letters.

Each of the next $m$ lines contains four integers $L$, $R$, $P$, $Q$ ($1 ≤ L ≤ R ≤ n, 1 ≤ P ≤ Q ≤ n$).

## Output

For each query, output the value of $\sum_{i=L}^{R}{f(X_i, P, Q)}$.

## Sample

InputOutput
5 1
agree
1 5 1 1

11


All the suffixes of "agree"

• $X_1 = \texttt{"agree"}$
• $X_2 = \texttt{"gree"}$
• $X_3 = \texttt{"ree"}$
• $X_4 = \texttt{"ee"}$
• $X_5 = \texttt{"e"}$

Now we are calculating

1. $f(X_1, 1, 1) = 4$ ("a", "g", "r" and "e" are the unique substring of length 1)
2. $f(X_2, 1, 1) = 3$ ("g", "r" and "e" are the unique substring of length 1)
3. $f(X_3, 1, 1) = 2$ ("r" and "e" are the unique substring of length 1)
4. $f(X_4, 1, 1) = 1$ ("e" is the unique substring of length 1)
5. $f(X_5, 1, 1) = 1$ ("e" is the unique substring of length 1)

So, answer is 4 + 3 + 2 + 1 + 1 = 11. ### Submit 