Problem B
Bona Fide

“Never attribute to malice that which is adequately explained by stupidity.” ­–Robert Hanlon.

A well-known trendsetter from a faraway land once needed strings with certain palindromic properties for inspiration. Unable to produce them all herself, she decided to outsource the work. To jog your memory, a palindrome is a string that reads the same forwards and backwards. For example, level and madam are palindromes, while label and maxim are not.

All was going well until the International Cheapskate Palindrome Company (ICPC), the company hired to produce the strings, made a huge blunder and delivered a string that was so horrible, the trendsetter lost all her inspiration. Now, she is suing the ICPC for damages resulting from lost productivity.

The ICPC was supposed to produce a palindrome-rich string­–a string which had many nonempty palindromic substrings. Recall that a substring of a string is a string that can be formed by removing zero or more characters from the start and end of the other string. For example, sig and design are substrings of design, while dig and singed are not.

As a lawyer for the ICPC, you need to show that the ICPC made a good faith effort to produce the required string. To this end, you want to show that while the string $S$ the ICPC produced may not be palindrome rich, it is almost palindrome-rich­–that is, it has many nonempty almost palindromic substrings. A string is called almost palindromic if it is either a palindrome, or can be turned into a palindrome by swapping two characters.

To strengthen your case, you will make $Q$ demonstrations. In the $i^\text {th}$ demonstration, you will consider only the $L_ i^\text {th}$ through $R_ i^\text {th}$ characters of $S$, and show that it is almost palindrome-rich by determining how many nonempty almost palindromic substrings it has.

Input

The first line of input contains two integers, $N$ ($1 \leq N \leq 200\, 000$) and $Q$ ($1 \leq Q \leq 200\, 000$), the length of $S$ and the number of demonstrations you will make, respectively.

The second line of input contains a string of $N$ lowercase Latin alphabet characters, describing the string $S$.

The next $Q$ lines contain the descriptions of the demonstrations. In particular, the $i^\text {th}$ of these lines contains two integers $L_ i$ and $R_ i$ ($1 \leq L_ i \leq R_ i \leq N$), denoting that for the $i^\text {th}$ demonstration, you will consider only the $L_ i^\text {th}$ through $R_ i^\text {th}$ characters of $S$.

Output

Output $Q$ lines. The $i^\text {th}$ of these lines should contain a single integer, the number of nonempty almost palindromic substrings in the $i^\text {th}$ demonstration.

9 3
beginning
1 5
4 8
1 9

5
11
16

6 1
velvet
1 6

7

10 6
abcdefghij
1 6
2 7
3 8
4 9
5 10
1 10

6
6
6
6
6
10