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.

你有一个长度为 $|s|$ 的字符串 $s = s_1s_2\ldots s_{|s|}$，由小写英文字母组成。此外还有 $q$ 个查询，每个查询由两个整数 $l_i,\,r_i$ 描述（满足 $1 \le l_i \le r_i \le |s|$）。查询的答案是字符串 $s[l_i\ldots r_i]$ 中回文子串的个数。

字符串 $s[l\ldots r] = s_ls_{l+1}\ldots s_r$（其中 $1 \le l \le r \le |s|$）是字符串 $s = s_1s_2\ldots s_{|s|}$ 的一个子串。

若字符串 $t$ 从左到右读与从右到左读完全相同，则称 $t$ 为回文串。形式化地，若 $t = t_1t_2\ldots t_{|t|} = t_{|t|}t_{|t|-1}\ldots t_1$。

The first line contains string s (1 ≤ |s| ≤ 5000). The second line contains a single integer q (1 ≤ q ≤ 106) — 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.

第一行包含字符串 $s$（$1 \leq |s| \leq 5000$）。第二行包含一个整数 $q$（$1 \leq q \leq 10^6$）—— 查询的个数。接下来 $q$ 行为查询内容。其中第 $i$ 行包含两个以空格分隔的整数 $l_i$、$r_i$（$1 \leq l_i \leq r_i \leq |s|$），表示第 $i$ 个查询。

保证给定字符串仅由小写英文字母组成。

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.

输出 q 个整数——即各查询的答案。按输入中查询给出的顺序输出答案。用空格分隔所输出的数字。

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

考虑第一个测试用例中的第四个查询。字符串 $s[4...6] = \text{«aba»}$。它的回文子串有：«a»、«b»、«a»、«aba»。