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,
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$).
For each query, output the value of $\sum_{i=L}^{R}{f(X_i, P, Q)}$.
Input | Output |
---|---|
5 1 agree 1 5 1 1 | 11 |
All the suffixes of "agree"
Now we are calculating
So, answer is 4 + 3 + 2 + 1 + 1 = 11. |