CF245H Queries for Number of Palindromes

You've got a string $ s=s_{1}s_{2}...\ s_{|s|} $ of length $ |s| $ , consisting of lowercase English letters. There also are $ q $ queries, each query is described by two integers $ l_{i},r_{i} $ $ (1

N/A

N/A

Consider the fourth query in the first test case. String $ s[4...\ 6] $ = «aba». Its palindrome substrings are: «a», «b», «a», «aba».