U369384 「魔术师-秘法师」

 > 不要救我！不要救我！不要救我！——伯特利 · 亚伯拉罕（又称“门”先生） 佛尔思 · 沃尔晋升成为「门」途径的半神「秘法师」后，终于摆脱了满月之夜的疯狂！她开始与月亮上的“门”先生交谈。 “听上去好像很有道理......但是我听不清啊！”

由于“门”先生被堕落母神绑架在星空，他与佛尔思的交谈很难进行。他只想对佛尔思说一句话。**我们下面将他想说的这句话称为「讯息」。** 佛尔思之所以难以听清，是因为星空常常会有**杂音**。如果在一秒中佛尔思听到了杂音，这些杂音会被佛尔思误认为是一个单词。尽管“门”先生的说话声能完全盖过杂音，佛尔思仍然不知道某一时刻究竟听到了杂音还是「讯息」。 佛尔思教你一个巧妙的方法来加以区分。当门先生话说完后，佛尔思会开始听到**回声**。神秘学中的回声与现实是不同的，简单地，「讯息」与回声按单词（而非发音）会构成一个回文串，但由于声音在神秘学中传播也需要时间，所以 **「讯息」与回声间会间隔一个单词的时间**，这短暂的瞬间听到的杂音被称为**对称点**。 佛尔思的记录时间足够长，因此她认为**对于记录下的一段字符，如果不存在对应的回声，它就不能作为「讯息」的一种可能。** 佛尔思记录下了她所听到的每个单词，用不同字母代替它们，把它们连起来变成了一个长度为 $n$ 的字符串 $s$。她想要知道「讯息」最长可能有多长？ 例如在 `eabcdcbaae` 中，「讯息」最长可能是 `abc`，长度为 $3$，此时我们认为 `d`、`e` 和第 $3$ 个 `a` 都是杂音，「讯息」的结束秒是第 $5$ 秒。 但是佛尔思觉得这个问题用不着你出手，她想考考你，她的问题是： **在所有可能的「讯息」中，长度最长的且对称点在第 $L_i$ 秒和第 $R_i$ 秒之间（包括 $L_i,R_i$）的句子的长度是多少？** 这样的问题有 $q$ 个。 ### 形式化题面： 给定一个的字符串 $s$，每次询问给出 $L_i,R_i$，要求输出当 $L_i\leq x\leq R_i$ 为何值时，存在最大的 $l$ 令对于任意 $1\leq k\leq l$ 都有 $s_{x-k}=s_{x+k}$。

输入共 $q+2$ 行。 第 $1$ 行一个长度若干的字符串 $s$，$s_i(1\leq i\leq n)$ 表示佛尔思听到第 $i$ 个单词。 第 $2$ 行一个正整数 $q$。 第 $3$ 到 $q+2$ 行每行 $2$ 个正整数 $L_j,R_j$，表示一个询问。

输出共 $q$ 行。 每行 $1$ 个整数，第 $j(1\leq j\leq q)$ 行表示第 $j$ 个询问的答案。如果没有找到符合要求的「讯息」，输出 $0$。

对于 $20\%$ 的数据，保证 $1\leq n,q\leq 2\times 10^2$。 对于 $50\%$ 的数据，保证 $1\leq n\leq 5\times 10^3$。 对于 $100\%$ 的数据，$1\leq L_i\leq R_i\leq n\leq 10^5,1\leq q\leq 5\times 10^5$，保证 $s$ 仅包含小写字母。