# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# 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 **suff _{i}**.

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

**L R P Q**: You need to calculate where

**f(suff**= number of unique substrings of

_{i}, P, Q)**suff**of length between

_{i}**P**to

**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 .

## Samples

Input | Output |
---|---|

5 1 agree 1 5 1 1 | 11 |

All the suffixes of **suff**= “agree”_{1}**suff**= “gree”_{2}**suff**= “ree”_{3}**suff**= “ee”_{4}**suff**= “e”_{5}
Now we are calculating **f(suff**= 4 (“a”, “g”, “r” and “e” are the unique substring of length 1)_{1}, 1, 1)**f(suff**= 3 (“g”, “r” and “e” are the unique substring of length 1)_{2}, 1, 1)**f(suff**= 2 (“r” and “e” are the unique substring of length 1)_{3}, 1, 1)**f(suff**= 1 (“e” is the unique substring of length 1)_{4}, 1, 1)**f(suff**= 1 (“e” is the unique substring of length 1)_{5}, 1, 1)
So, answer is 4 + 3 + 2 + 1 + 1 = 11 |

Login to submit