30423번 - String 다국어

문제

Little Y is a college student who is currently doing researches related to strings. Little Y learned about the following definitions regarding strings:

• Given a string $s[1 : n]$ of length $n,ドル we define its substring $s[l : r] (1 \leq l \leq r \leq n)$ as the new string obtained by selecting $s[l], s[l + 1], \dots , s[r]$ in order and concatenating them.
• Given a string $s[1 : n]$ of length $n,ドル we define its reversed result $R(s)$ as the string obtained by concatenating $s[n], s[n - 1], \dots , s[1]$ in order, which is the string obtained by reversing the original string.
• Given two strings $a[1 : n]$ and $b[1 : n]$ of equal length $n,ドル we define $a$ to be lexicographically smaller than $b$ if and only if there exists 1ドル \leq i \leq n$ such that for any 1ドル \leq j < i, a[j] = b[j],ドル and $a[i] < b[i]$.

After understanding the above definitions, Little Y came up with the following problem:

Given a string $s[1 : n]$ of length $n,ドル there are $q$ queries, each query giving two parameters $i$ and $r$. You need to find out how many values of $l$ satisfy the following conditions:

• 1ドル \leq l \leq r$.
• $s[i : i + l - 1]$ is lexicographically smaller than $R(s[i + l : i + 2l - 1])$.

Little Y would like to ask for your help in solving this problem.

입력

This problem has multiple test data sets.

The first line of the input contains two integers $c $ and $t,ドル which represent the test case number and the number of test data sets. $c = 0$ represents that this test case is a sample test.

Then, each set of test data is given as input in order. For each set of test data:

The first line of input contains two positive integers, $n$ and $q,ドル which represent the length of the string and the number of queries respectively.

The second line of input contains a string $s$ of length $n$ that only consists of lowercase letters.

Then $q$ lines follow, each containing two positive integers, $i$ and $r,ドル representing a query. It is guaranteed that $i+2r -1 \leq n$.

출력

For each query of each set of test data, output a line containing an integer, representing the number of $l$s satisfying the requirements.

제한

For all test data, it is guaranteed that: 1ドル \leq t\leq 5,1\leq n\leq 10^5,1\leq q\leq 10^5,1\leq i+2r-1\leq n$. The string $s$ only consists of lowercase letters.

힌트

추가 예제

samples.zip