Description

Bob likes strings.

Bob thinks that a string repeated twice is beautiful. For example, aa, sese, abcabc, baabaa, abababab are beautiful strings, while ab, aadead, sesese, abba are not. More specifically, if a string $S$ can be written as the concatenation of two identical strings, that is, there exists a string $P$ such that $S = PP$, then $S$ is beautiful.

Bob has a string $T = T_1 T_2 \cdots T_n$ of length $n$. Now he wants to know: given a substring $Q = T[l \cdots r]$ of $T$, how many essentially different beautiful strings appear as substrings within this substring $Q$. If two strings are the same but occur at different positions, then they are not considered essentially different.

Bob has $q$ different queries in total. You need to compute the answers quickly.

Input Format

The first line contains two integers $n, q$. The second line contains a string $T$ consisting only of lowercase letters a and b.

In the next $q$ lines, each line contains two integers $l, r$, representing one query.

Output Format

Output $q$ lines, each with one integer representing the answer.

11 5
aabaabaaaab
1 11
1 6
7 10
5 5
3 8

5
2
2
0
2

Hint

Sample explanation 1:

In $T$, the essentially different beautiful strings are aa, aaaa, abaaba, aabaab, baabaa.

Sample input/output 2 is provided in the attachment.

Constraints:

For the first $10\%$ of the testdata, $n \leq 100$.

For the first $20\%$ of the testdata, $n \leq 500$.

For the first $40\%$ of the testdata, $n \leq 5000$.

For another $20\%$ of the testdata, it is guaranteed that the total number of beautiful substrings in $T$ does not exceed $10^6$, where substrings at different positions are considered different.

For another $20\%$ of the testdata, $q = 1$.

For $100\%$ of the testdata, $1 \leq n, q \leq 200000$, $1 \leq l \leq r \leq n$. $T$ contains only lowercase letters a and b.

Translated by ChatGPT 5