crashed nb/se 不过它解释为什么跳 \(k\bmod d+d\) 确实有点迷，不懂为什么直接跳 \(k\bmod d\) 会挂可以手摸一下峰峰峰的 hack，从 25 开始跳。
简单做法就是建出失配树然后跳 LCA．但是 border 的性质很好，所以就来考虑一些小常数做法：
前面讲的 border 划分都没有细讲怎么构造出这些等差数列，一个直接的构造是倍增分块，\([1,2),[2,4),[4,8)\cdots,[2^k,2^{k+1}),\cdots\) 这么分块，然后断言每一块里面的 border 一定形成了一个等差数列。首先最后一块肯定满足，\(\geq \lceil\frac{|s|}{2}\rceil\) 的 border 形成一个等差数列，对于中间的块同理，也就是对 \(s[:2^{k+1}]\) 用那个结论。
这个构造好像不太能改改支持查 LCA．还是考虑一个等差数列在支配树上实际上就是一条链，而且端点具有祖孙关系。那么自然就想到了树链剖分，尝试利用 border 划分将整棵树进行剖分，使得从每个点往上跳一个树链相当于跳一个等差数列。那么问题就是怎么剖，怎么确定两个点是否在同一个等差数列上。
怎么剖，实际上就是对于一个 \(k\)，确定 \(k\) 所在的等差数列的头在哪里。
- \(nxt_k\leq \lfloor\frac{k}{2}\rfloor\)：它就是链头。
- 否则，对于最短周期 \(d=k-nxt_k\)：考虑每次将 \(k\gets k-d\)，当 \(d\leq \lfloor\frac{k}{2}\rfloor\) 的时候根据推 border 理论时的引理，\(k-d\) 就是 \(k\) 最长 border．否则就到了链头。考虑 \(k\bmod d\)，不断 \(-d\) 的过程，只有最后一步会出现问题，所以链头就是 \(k\bmod d+d\)．
然后问题就是怎么判终止条件，以及会不会出现跳过 LCA 的情况
判终止直接看 \(x\equiv y\pmod d\) 是否成立就行，这里 \(x>y,d=x-nxt_x\)。如果不成立那么肯定不在同一个划分出的链上。如果成立，画图可知 \(y\) 是 \(x\) 的 border，所以 \(y\) 就是 \(x\) 的祖先，而且 \(x,y\) 在同一条划分出的链上时一定能判出来。注意这里严格来说并不是看它们两个是否在同一个等差数列上。
还是峰峰峰那个例子，树链是 \(1\leftrightarrow 3\leftrightarrow 7\leftrightarrow 13\leftrightarrow 19\leftrightarrow 25\)，1 和 25 能判对，7 和 25 能判对，但是 3 和 25 判不出。但是只要保证 \(7\leftrightarrow 13\leftrightarrow 19\leftrightarrow 25\) 这条划分出的链上的点都能判出来，并且不会额外判错就行。
#include<bits/stdc++.h>
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<typename T>
T &read(T &r){
r=0;bool w=0;char ch=getchar();
while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
return r=w?-r:r;
}
const int N=1000010;
int n,m,nxt[N];
char s[N];
signed main(){
char c=getchar();
while(c>='a'&&c<='z')s[++n]=c,c=getchar();
read(m);
for(int i=2,j=0;i<=n;i++){
while(j&&s[j+1]!=s[i])j=nxt[j];
if(s[j+1]==s[i])++j;
nxt[i]=j;
}
while(m--){
int x,y;
read(x);read(y);
x=nxt[x];y=nxt[y];
while(x&&y&&x!=y){
if(x<y)swap(x,y);
int d=x-nxt[x];
if(nxt[x]>(x>>1)){
if(x%d==y%d)break;
x=nxt[x%d+d];
}
else x=nxt[x];
}
cout << min(x,y) << '\n';
}
return 0;
}