# 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

By emrul_mu · 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 suffi.

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

L R P Q: You need to calculate where f(suffi, P, Q) = number of unique substrings of suffi of length between P to Q.

## Input

The first line of the input is followed by two integers n (1 ≤ n ≤ 103) and m (1 ≤ m ≤ 106).

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

InputOutput
```5 1
agree
1 5 1 1
```
```11
```

All the suffixes of “agree”

• suff1 = “agree”
• suff2 = “gree”
• suff3 = “ree”
• suff4 = “ee”
• suff5 = “e”

Now we are calculating

1. f(suff1, 1, 1) = 4 (“a”, “g”, “r” and “e” are the unique substring of length 1)
2. f(suff2, 1, 1) = 3 (“g”, “r” and “e” are the unique substring of length 1)
3. f(suff3, 1, 1) = 2 (“r” and “e” are the unique substring of length 1)
4. f(suff4, 1, 1) = 1 (“e” is the unique substring of length 1)
5. f(suff5, 1, 1) = 1 (“e” is the unique substring of length 1)

So, answer is 4 + 3 + 2 + 1 + 1 = 11

Discussion