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
Input  Output 

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  $f(X_1, 1, 1) = 4$ ("a", "g", "r" and "e" are the unique substring of length 1)
 $f(X_2, 1, 1) = 3$ ("g", "r" and "e" are the unique substring of length 1)
 $f(X_3, 1, 1) = 2$ ("r" and "e" are the unique substring of length 1)
 $f(X_4, 1, 1) = 1$ ("e" is the unique substring of length 1)
 $f(X_5, 1, 1) = 1$ ("e" is the unique substring of length 1)
So, answer is 4 + 3 + 2 + 1 + 1 = 11. 
Factors
 CPU  Memory  Source 

Bash 5.0  1×  1×  1× 
Brainf*ck  1×  1×  1× 
C# Mono 6.0  1×  1×  1× 
C++11 GCC 7.4  1×  1×  1× 
C++14 GCC 8.3  1×  1×  1× 
C++17 GCC 9.2  1×  1×  1× 
C++20 GCC 12.1  1×  1×  1× 
C11 GCC 12.1  1×  1×  1× 
C11 GCC 9.2  1×  1×  1× 
Common Lisp SBCL 2.0  1×  1×  1× 
Erlang 22.3  1×  1×  1× 
Free Pascal 3.0  1×  1×  1× 
Go 1.18  1×  1×  1× 
Haskell 8.6  1×  1×  1× 
Java 1.8  1×  1×  1× 
Kotlin 1.1  1×  1×  1× 
Lua 5.4  1×  1×  1× 
Node.js 10.16  1×  1×  1× 
Perl 5.30  1×  1×  1× 
PHP 7.2  1×  1×  1× 
PyPy 7.1 (2.7)  2×  1×  1× 
PyPy 7.1 (3.6)  2×  1×  1× 
Python 2.7  2×  1×  1× 
Python 3.7  2×  1×  1× 
Ruby 2.6  2×  1×  1× 
Rust 1.57  1×  1×  1× 
Swift 5.3  1×  1×  1× 
Whitespace  1×  1×  1× 