← 返回题目列表

Codeforces · 245/H

H. 回文数查询

中文机器翻译题面 查看原题

你有一个字符串 s = s1s2... s|s|长度|s|,由小写英文字母组成。还有 q 个查询,每个查询由两个整数 li, ri (1 ≤ li ≤ ri ≤ |s|) 描述。查询的答案是字符串 s[li...ri] 的子串数量,这些子串是回文。

字符串 s[l... r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) 是字符串 s = s1s2... s|s| 的子字符串。

如果字符串 t 从左到右和从右到左读取相同,则称为回文。形式上,如果 t = t1t2... t|t| = t|t|t|t| - 1...t1。

输入

第一行包含字符串 s (1 ≤ |s| ≤ 5000)。第二行包含一个整数 q (1 ≤ q ≤ 106) — 查询数。接下来的 q 行包含查询。这些行中的第 i 行包含两个以空格分隔的整数 li, ri (1 ≤ li ≤ ri ≤ |s|) — 第 i 个查询的描述。

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

输出

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

示例

输入 #1

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

输出 #1

1
7
3
4
2

注意

考虑第一个测试用例中的第四个查询。字符串 s[4...6] = «aba»。它的回文子串是:《a》、《b》、《a》、《aba》。