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