Queries for Number of Palindromes

题目描述 给你一个字符串s由小写字母组成，有q组询问，每组询问给你两个数，l和r，问在字符串区间l到r的字串中，包含多少回文串。 输入格式 第1行，给出s，s的长度小于5000 第2行给出q(1<=q<=10^6) 第2至2+q行 给出每组询问的l和r 输出格式 输出每组询问所问的数量。

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.

caaaba
5
1 1
1 4
2 3
4 6
4 5

1
7
3
4
2

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