Unique Substrings Query

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

5 1
agree
1 5 1 1

11