Problem1088--回文串询问Ⅱ

1088: 回文串询问Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 349  Solved: 157
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI要考考你对回文串的掌握了~ 
现在有一个长度为n的字符串S,PIPI对此有q个询问,每次询问S中某个连续区间(从1开始)中回文子串的数目。 

Input

多组数据。 
第一行为两个个整数n,q(1<=n<=1000,1<=q<=100000) 
第二行为一个长为n的字符串S。 
接下来q行,每行两个整数l,r,表示询问S中区间[l,r]中回文子串的数目。保证l<=r且合法。 

Output

对于每个询问输出占一行,输出该区间内回文子串的数目。 

Sample Input

3 3
aba
1 3
1 2
2 2

Sample Output

4
2
1

HINT

aba中有a,b,c,aba四个回文子串

Source/Category