# 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.

Sample Input 1 | Sample Output 1 |
---|---|

9 3 beginning 1 5 4 8 1 9 |
5 11 16 |

Sample Input 2 | Sample Output 2 |
---|---|

6 1 velvet 1 6 |
7 |

Sample Input 3 | Sample Output 3 |
---|---|

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