问题 28532 --B-Scope乙己

28532: B-Scope乙己

时间限制: 10 Sec  内存限制: 512 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS0元][下载测试数据0元][20910kb]

题目描述

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 的长度。

输入

第一行一个字符串 S 。

第二行一个整数 q 表示询问个数。

接下来的 q 行每行两个整数 l,r 表示一个询问。

输出

对于每组询问输出答案。

样例输入

abbabbaa
3
1 8
1 7
2 7

样例输出

1
4
3

提示

数据范围



对于 30% 的数据, n,q<=1000 。



对于 50% 的数据, n,q<=20000 。



对于另外 30% 的数据,答案至少为 r-l+1 的一半。



对于 100% 的数据, n,q<=10^5 。

来源

[提交][状态]