1180: B-Scope乙己
Memory Limit：512 MB
Time Limit：10.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：1
Description
Scape 一到机房，所有做题的人便都看着他笑，有的叫道，“Scape，你一定又被标准分倍杀了！”他不回答，对柜里说，“测两个程序，看一眼成绩单。”便拷出两个程序。他们又故意的高声嚷道，“你怎么欧拉回路和逆序对都WA了！”……
Scape 知道，以上的故事只是 OI 生涯里的一个意外，为了证明自己，他决定教你 Border 的四种求法。
给一个小写字母字符串 S ，q 次询问每次给出 l,r ，求 s[l..r] 的 Border 。
Border: 对于给定的串 s ，最大的 i 使得 s[1..i] = s[|s|-i+1..|s|], |s| 为 s 的长度。
Scape 知道，以上的故事只是 OI 生涯里的一个意外，为了证明自己，他决定教你 Border 的四种求法。
给一个小写字母字符串 S ，q 次询问每次给出 l,r ，求 s[l..r] 的 Border 。
Border: 对于给定的串 s ，最大的 i 使得 s[1..i] = s[|s|-i+1..|s|], |s| 为 s 的长度。
Input
第一行一个字符串 S 。
第二行一个整数 q 表示询问个数。
接下来的 q 行每行两个整数 l,r 表示一个询问。
第二行一个整数 q 表示询问个数。
接下来的 q 行每行两个整数 l,r 表示一个询问。
Output
对于每组询问输出答案。
Sample Input Copy
abbabbaa
3
1 8
1 7
2 7
Sample Output Copy
1
4
3
HINT
数据范围
对于 30% 的数据， n,q<=1000 。
对于 50% 的数据， n,q<=20000 。
对于另外 30% 的数据，答案至少为 r-l+1 的一半。
对于 100% 的数据， n,q<=10^5 。
对于 30% 的数据， n,q<=1000 。
对于 50% 的数据， n,q<=20000 。
对于另外 30% 的数据，答案至少为 r-l+1 的一半。
对于 100% 的数据， n,q<=10^5 。