Question
Palindrome Substring Count in Range Queries
You are given a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression consisting of lowercase English letters. You are also given KaTeX can only parse string typed expression queries.
In each query, two indices KaTeX can only parse string typed expression and KaTeX can only parse string typed expression (0-indexed) are given. Your task is to determine the total number of palindromic substrings present completely inside the substring KaTeX can only parse string typed expression.
A substring KaTeX can only parse string typed expression is called a palindrome if it reads the same forward and backward.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the length of the string and the number of queries.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — representing the query range.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — representing the query range.
Output
For each query, print a single integer — the total number of palindromic substrings present in KaTeX can only parse string typed expression.
Example
Input
6 3
ababae
0 2
1 4
0 5
Output
4
6
10
Explanation
Query (0, 2) → substring = "aba"
Palindromic substrings:
"a", "b", "a", "aba"
Total = 4
Query (1, 4) → substring = "baba"
Palindromic substrings:
"b", "a", "b", "a", "bab", "aba"
Total = 6
Query (0, 5) → substring = "ababae"
Palindromic substrings include:
"a", "b", "a", "b", "a", "e", "aba", "bab", "aba", "ababa"
Total = 10
6 3
ababae
0 2
1 4
0 5
Output
4
6
10
Explanation
Query (0, 2) → substring = "aba"
Palindromic substrings:
"a", "b", "a", "aba"
Total = 4
Query (1, 4) → substring = "baba"
Palindromic substrings:
"b", "a", "b", "a", "bab", "aba"
Total = 6
Query (0, 5) → substring = "ababae"
Palindromic substrings include:
"a", "b", "a", "b", "a", "e", "aba", "bab", "aba", "ababa"
Total = 10