Unique Substrings Query

emrul_mu #HelpFloodVictims Program...
Limits 1s, 128 MB

You will be given a string ss of length nn.

Consider substring s[i,n]s[i, n] (where ii is the starting position and nn is the ending position) of ss as a string called XiX_i.

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

L R P Q

For each query, you need to calculate:

i=LRf(Xi,P,Q)\sum_{i=L}^{R}{f(X_i, P, Q)}

Where,

  • f(Xi,P,Q)f(X_i, P, Q) is the number of unique substrings of XiX_i of length between PP and QQ.

Input

The first line of the input is followed by two integers nn (1n1031 ≤ n ≤ 10^3) and mm (1m1061 ≤ m ≤ 10^6).

The second line contains the string ss of only lowercase letters.

Each of the next mm lines contains four integers LL, RR, PP, QQ (1LRn,1PQn1 ≤ L ≤ R ≤ n, 1 ≤ P ≤ Q ≤ n).

Output

For each query, output the value of i=LRf(Xi,P,Q)\sum_{i=L}^{R}{f(X_i, P, Q)}.

Sample

InputOutput
5 1
agree
1 5 1 1
11

All the suffixes of "agree"

  • X1="agree"X_1 = \texttt{"agree"}
  • X2="gree"X_2 = \texttt{"gree"}
  • X3="ree"X_3 = \texttt{"ree"}
  • X4="ee"X_4 = \texttt{"ee"}
  • X5="e"X_5 = \texttt{"e"}

Now we are calculating

  1. f(X1,1,1)=4f(X_1, 1, 1) = 4 ("a", "g", "r" and "e" are the unique substring of length 1)
  2. f(X2,1,1)=3f(X_2, 1, 1) = 3 ("g", "r" and "e" are the unique substring of length 1)
  3. f(X3,1,1)=2f(X_3, 1, 1) = 2 ("r" and "e" are the unique substring of length 1)
  4. f(X4,1,1)=1f(X_4, 1, 1) = 1 ("e" is the unique substring of length 1)
  5. f(X5,1,1)=1f(X_5, 1, 1) = 1 ("e" is the unique substring of length 1)

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


Submit

Login to submit.

Statistics

76% Solution Ratio
kzvd4729Earliest, Aug '19
Rawaha0909Fastest, 0.2s
samiulsamiLightest, 12 MB
sakib_muhitShortest, 979B
Toph uses cookies. By continuing you agree to our Cookie Policy.