# Practice on Toph

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

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

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:

The first line of the input is followed by two integers **n (1 ≤ n ≤ 10 ^{3})** and

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 .

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 |

80% Solution Ratio

kzvd4729Earliest,

Uniquepro.Fastest, 0.2s

aniks2645Lightest, 14 MB

tahsin_protikShortest, 1229B

Login to submit