F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 5036. -- [Jsoi2014]回文串

5036: [Jsoi2014]回文串

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 32  Solved: 16
[Submit][Status][Discuss]

Description

JYY又重新切换到计算机科学家状态并幵始研宄回文串啦!不过呢,很长的回文串对脑袋不太够用的JYY来说有点棘
手,所以请你帮忙。JYY现在有一个由小写字母组成的字符串S。我们用S[i,j]表示S中从第i个字符到第j个字符所
组成的子串(字符串下标从1开始)。现在JYY有Q个询问,其中第i个询问(Li,Ri)需要统计满足如下条件的子串S[x,y
]的数量:
1、 Li ≤ x ≤ y ≤ Ri。
2、 S[x,y]是回文串。
请你帮助JYY计算这Q个询问的答案。

Input

第一行包含一个字符串S;
第二行包含一个正整数Q;
接下来Q行,每行两个整数Li和Ri。
对于所有数据满足:1≤|S|≤10^5 & 1≤Q≤3*10^5 & 1≤Li≤Ri≤|S|

Output

输出包含Q行,每行个一个整数,第i行的整数为第i个询问的答案。

Sample Input

abaa
4
1 2
1 3
1 4
3 4

Sample Output

2
4
6
3

HINT

Source

Round3

[Submit][Status][Discuss]

HOME Back