样例都不过qwq

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+3,M=2e6+4;
struct edge{int to,nxt;}E[M];
int kmp[N],head[N],tot=1,q;
int fa[N],dep[N],hson[N],size[N],dfn[N],top[N],idx=0;
string s;
inline void add(int u,int v){
	E[++tot].nxt=head[u];
	E[head[u]=tot].to=v;
	return;
}
inline void dfs1(int u=1,int f=0){
	dep[u]=dep[fa[u]=f]+(size[u]=1);
	for(int i=head[u],v;i;i=E[i].nxt){
		v=E[i].to;
		if(v==f) continue;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>size[hson[u]]) hson[u]=v;
	}
	return;
}
inline void dfs2(int u=1,int t=0){
	top[u]=t,dfn[u]=++idx;
	if(!hson[u]) return;
	dfs2(hson[u],t);
	for(int i=head[u],v;i;i=E[i].nxt){
		v=E[i].to;
		if(v==fa[u]||v==hson[u]) continue;
		dfs2(v,v);
	}
	return;
}
inline void build(){
	int i=0,j=kmp[0]=-1;
	while(i<s.size()){
		if(!~j||s[i]==s[j]) kmp[++i]=++j;
		else j=kmp[j];
	}
	for(int i=1;i<s.size();++i) add(kmp[i],i),add(i,kmp[i]);
	hson[0]=1,size[0]=1+size[1],dep[0]=0,top[0]=0,fa[0]=0,dfn[0]=0;
	dfs1(),dfs2();
	return;
}
inline int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]? x:y;
}
signed main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>s>>q;
	build();
	for(int x,y;q--;){
		cin>>x>>y;
		cout<<LCA(x,y)<<'\n';
	}
	return 0;
}