P4482 [BJWC2018] Border 的四种求法

Scape 一到机房，所有做题的人便都看着他笑，有的叫道，“Scape，你一定又被标准分倍杀了！”他不回答，对柜里说，“测两个程序，看一眼成绩单。”便拷出两个程序。他们又故意的高声嚷道，“你怎么欧拉回路和逆序对都WA了！”……

Scape 知道，以上的故事只是 OI 生涯里的一个意外，为了证明自己，他决定教你 $\text{Border}$ 的四种求法。 给一个小写字母字符串 $S$，$q$ 次询问每次给出 $l,r$ ，求 $s_{l\ldots r}$ 的 $\text{Border}$。 $\text{Border}$：对于给定的串 $s$，最大的 $i$ 使得 $s_{1\ldots i} = s_{|s|-i+1\ldots |s|}$。$|s|$ 为 $s$ 的长度。

无

无

对于 $30%$ 的数据， $n,q\leq 1000$ 。 对于 $50%$ 的数据， $n,q\leq 2\times 10^4$ 。 对于另外 $30\%$ 的数据，答案至少为 $r-l+1$ 的一半。 对于 $100\%$ 的数据， $n,q\leq 2\times 10^5$ 。