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<=l_{i}<=r_{i}<=|s|)$ . The answer to the query is the number of substrings of string $s[l_{i}...\ r_{i}]$ , which are palindromes.

String $s[l...\ r]=s_{l}s_{l+1}...\ s_{r}$ $(1<=l<=r<=|s|)$ is a substring of string $s=s_{1}s_{2}...\ s_{|s|}$ .

String $t$ is called a palindrome, if it reads the same from left to right and from right to left. Formally, if $t=t_{1}t_{2}...\ t_{|t|}=t_{|t|}t_{|t|-1}...\ t_{1}$ .

The first line contains string $s$ $(1<=|s|<=5000)$ . The second line contains a single integer $q$ $(1<=q<=10^{6})$ — the number of queries. Next $q$ lines contain the queries. The $i$ -th of these lines contains two space-separated integers $l_{i},r_{i}$ $(1<=l_{i}<=r_{i}<=|s|)$ — the description of the $i$ -th query.

It is guaranteed that the given string consists only of lowercase English letters.

Print $q$ integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.

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