#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=3e6+5,M=1e6+3,logN=21;
int n,T,len[M],vis[N<<1],tmp[N<<1];LL ans;char s[M];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
vector<int>Q[M];
struct Suffix_Automaton{
int O,last,siz[N<<1],link[N<<1],maxlen[N<<1];map<int,int>trans[N<<1];
Suffix_Automaton(){O=1;}
inline int insert(Re ch,Re op,Re last){
if(trans[last].find(ch)!=trans[last].end()){
Re p=last,x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])return x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(map<int,int>::iterator it=trans[x].begin();it!=trans[x].end();++it)trans[y].insert(*it);
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[x]=y;
return y;
}
}
Re z=++O,p=last;if(op)siz[z]=1;maxlen[z]=maxlen[p]+1;
while(p&&trans[p].find(ch)==trans[p].end())trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
Re x=trans[p][ch];
if(maxlen[x]==maxlen[p]+1)link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(map<int,int>::iterator it=trans[x].begin();it!=trans[x].end();++it)trans[y].insert(*it);
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[x]=link[z]=y;
}
}
return z;
}
int o,head[N<<1];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void dfs(Re x){
for(Re i=head[x];i;i=a[i].next)dfs(a[i].to),siz[x]+=siz[a[i].to];
}
inline void build(){
for(Re i=2;i<=O;++i)add(link[i],i);dfs(1);
}
inline int ask(Re p,Re len){
while(maxlen[link[p]]>=len)p=link[p];return p;
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
scanf("%s",s+1),n=strlen(s+1),in(T);
for(Re i=1,last=1;s[i];++i)last=SAM.insert(s[i]-'a',1,last);
for(Re i=1;i<=T;++i){
scanf("%s",s+1),len[i]=strlen(s+1);Re last=1;
for(Re j=1;j<len[i];++j)last=SAM.insert(s[j]-'a',0,last);
Q[i].push_back(last=SAM.insert(s[len[i]]-'a',0,last));
for(Re j=1;j<len[i];++j)Q[i].push_back(last=SAM.insert(s[j]-'a',0,last));
}
SAM.build();
for(Re i=1;i<=T;++i){
tmp[0]=ans=0;
for(Re j=0,SZ=Q[i].size();j<SZ;++j){
Re x=SAM.ask(Q[i][j],len[i]);
if(vis[x])continue;
tmp[++tmp[0]]=x,vis[x]=1,ans+=SAM.siz[x];
}
for(Re j=1;j<=tmp[0];++j)vis[tmp[j]]=0;
printf("%lld\n",ans);
}
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+5;
int n,t,T,Len[N];char s[N],ch[360003];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Suffix_Automaton{
int O,cnt[N],link[N],maxlen[N],trans[N][26];
Suffix_Automaton(){O=1;}
inline int insert(Re ch,Re last){
if(trans[last][ch]&&maxlen[last]+1==maxlen[trans[last][ch]])return trans[last][ch];
Re x,y,z=++O,p=last,flag=0;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
if(maxlen[p]+1==maxlen[z]/*�����p==last*/)flag=1;
y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return flag?y:z;
}
int co[N];
inline void updata(Re p,Re id){
while(p&&co[p]!=id)++cnt[p],co[p]=id,p=link[p];
}
inline void ask(char ch[]){
Re p=1,flag=1;
for(Re i=1;ch[i]&&flag;++i){
Re a=ch[i]-'a';
if(trans[p][a])p=trans[p][a];
else flag=0;
}
printf("%d\n",flag?cnt[p]:0);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i){
scanf("%s",ch+1);Re last=1;
for(Re j=1;ch[j];Len[i]=j,++j)last=SAM.insert(s[++t]=ch[j]-'a',last);
}
for(Re i=1,t=0;i<=n;++i)
for(Re j=1,p=1;j<=Len[i];++j)
SAM.updata(p=SAM.trans[p][s[++t]],i);
while(T--)scanf("%s",ch+1),SAM.ask(ch);
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+5;
int n,t,T,Len[N];char s[N],ch[360003];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Trie{
int O,c[N],fa[N],tr[N][26];
Trie(){O=1;}
inline void insert(char ch[],Re id){
Re p=1;
for(Re i=1;ch[i];Len[id]=i,++i){
Re a=ch[i]-'a';s[++t]=a;
if(!tr[p][a])tr[p][a]=++O,fa[O]=p,c[O]=a;
p=tr[p][a];
}
}
}T1;
struct Suffix_Automaton{
int O,pos[N],cnt[N],link[N],maxlen[N],trans[N][26];queue<int>Q;
Suffix_Automaton(){O=1;}
inline int insert(Re ch,Re last){
Re x,y,z=++O,p=last,flag=0;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return flag?y:z;
}
int co[N];
inline void updata(Re p,Re id){
while(p&&co[p]!=id)++cnt[p],co[p]=id,p=link[p];
}
inline void build(){
for(Re i=0;i<26;++i)if(T1.tr[1][i])Q.push(T1.tr[1][i]);
pos[1]=1;
while(!Q.empty()){
Re x=Q.front();Q.pop();
pos[x]=insert(T1.c[x],pos[T1.fa[x]]);
for(Re i=0;i<26;++i)if(T1.tr[x][i])Q.push(T1.tr[x][i]);
}
for(Re i=1,t=0;i<=n;++i)
for(Re j=1,p=1;j<=Len[i];++j)
updata(pos[p=T1.tr[p][s[++t]]],i);
}
inline void ask(char ch[]){
Re p=1,flag=1;
for(Re i=1;ch[i]&&flag;++i){
Re a=ch[i]-'a';
if(trans[p][a])p=trans[p][a];
else flag=0;
}
printf("%d\n",flag?cnt[p]:0);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i)scanf("%s",ch+1),T1.insert(ch,i);
SAM.build();
while(T--)scanf("%s",ch+1),SAM.ask(ch);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+3;
int n;char ch[N*10];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct AC_Automaton{
int O,edp[N],fail[N],tr[N][26];queue<int>Q;
AC_Automaton(){O=1;}
inline void insert(char ch[],Re id){
Re p=1;
for(Re i=1;ch[i];++i){
Re a=ch[i]-'a';
if(!tr[p][a])tr[p][a]=++O;
p=tr[p][a];
}
edp[id]=p;
}
inline void get_fail(){
for(Re i=0;i<26;++i)tr[0][i]=1;
Q.push(1);
while(!Q.empty()){
Re x=Q.front();Q.pop();
for(Re i=0;i<26;++i)
if(tr[x][i])fail[tr[x][i]]=tr[fail[x]][i],Q.push(tr[x][i]);
else tr[x][i]=tr[fail[x]][i];
}
}
int ru[N],cnt[N];
inline void sakura(char ch[]){
for(Re i=1,p=1;ch[i];++i)p=tr[p][ch[i]-'a'],++cnt[p];
for(Re i=2;i<=O;++i)++ru[fail[i]];
for(Re i=1;i<=O;++i)if(!ru[i])Q.push(i);
while(!Q.empty()){
Re x=Q.front();Q.pop();
cnt[fail[x]]+=cnt[x];
if(!(--ru[fail[x]]))Q.push(fail[x]);
}
for(Re i=1;i<=n;++i)printf("%d\n",cnt[edp[i]]);
}
}AC;
int main(){
// freopen("123.txt","r",stdin);
in(n);
for(Re i=1;i<=n;++i)scanf("%s",ch+1),AC.insert(ch,i);
AC.get_fail();
scanf("%s",ch+1);AC.sakura(ch);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=12e5+3;
int T,ans,mask;char op[10],s[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline string In(Re mask){
scanf("%s",s);string chars=s;
for(int j=0;j<chars.length();j++){
mask=(mask*131+j)%chars.length();
char t=chars[j];
chars[j]=chars[mask];
chars[mask]=t;
}
return chars;
}
struct Suffix_Automaton{
struct Link_Cut_Tree{
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
int Q[N];
struct QAQ{int fa,ans,add,ps[2];}tr[N];
inline void add(Re p,Re v){tr[p].ans+=v,tr[p].add+=v;}
inline void pushdown(Re p){
Re v=tr[p].add;
if(v){
if(pl)add(pl,v);
if(pr)add(pr,v);
tr[p].add=0;
}
}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(nort(x))Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p){for(Re son=0;p;son=p,p=pf)splay(p),pr=son;}
inline void link(Re x,Re y){tr[x].fa=y,access(y),splay(y),add(y,tr[x].ans);}
inline void cut(Re x){
access(x),splay(x),add(tr[x].ps[0],-tr[x].ans);
tr[tr[x].ps[0]].fa=0,tr[x].ps[0]=0;
}
inline int ask(Re x){splay(x);return tr[x].ans;}
}LCT;
int O,last,link[N],maxlen[N],trans[N][30];
Suffix_Automaton(){last=O=1;}
inline void insert(char ch){
Re z=++O,p=last;LCT.tr[z].ans=1,maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1,LCT.link(z,1);
else{
Re x=trans[p][ch];
if(maxlen[x]==maxlen[p]+1)link[z]=x,LCT.link(z,x);
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],LCT.cut(x),LCT.link(y,link[y]);
link[x]=link[z]=y,LCT.link(x,y),LCT.link(z,y);
}
}
last=z;
}
inline void add(string ch){
for(Re i=0;ch[i];++i)insert(ch[i]-'A');
}
inline int ask(string ch){
Re p=1;
for(Re i=0;ch[i];++i)if(!(p=trans[p][ch[i]-'A']))return 0;
return LCT.ask(p);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
in(T),scanf("%s",s+1);
for(Re i=1;s[i];++i)SAM.insert(s[i]-'A');
while(T--){
scanf("%s",op);string s=In(mask);
if(op[0]=='A')SAM.add(s);
else mask^=(ans=SAM.ask(s)),printf("%d\n",ans);
}
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5;
char ch[2000003];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Suffix_Automaton{
int O,last,ru[N],siz[N],link[N],maxlen[N],minlen[N],trans[N][26];queue<int>Q;
Suffix_Automaton(){last=O=1;}
inline void insert(char ch){
Re z=++O,p=last;siz[z]=1,maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;//û�ҵ�trans[...][ch]
else{
Re x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x];
link[z]=link[x]=y;
}
}
last=z;
}
inline void Tuopu(){
for(Re i=2;i<=O;++i)++ru[link[i]];
for(Re i=1;i<=O;++i)if(!ru[i])Q.push(i);
while(!Q.empty()){
Re x=Q.front();Q.pop();
siz[link[x]]+=siz[x];
if(!(--ru[link[x]]))Q.push(link[x]);
}
}
inline void sakura(){
for(Re i=2;i<=O;++i)minlen[i]=maxlen[link[i]]+1;
Tuopu();Re ans=0;
for(Re i=1;i<=O;++i)if(siz[i]>1)ans=max(ans,siz[i]*maxlen[i]);
printf("%d\n",ans);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
scanf("%s",ch+1);
for(Re i=1;ch[i];++i)SAM.insert(ch[i]-'a');
SAM.sakura();
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=4e5+10;
int n,x,y,T;LL P,M,G,K;char s[N>>1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Sakura2{
int O,last,pos[N],siz[N],link[N],maxlen[N],trans[N][26];
// siz[x]: 节点x的出现次数 (endpos的大小)
inline void insert(Re ch,Re id){
Re z=++O,p=last;pos[z]=id,siz[z]=1,maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
Re x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1,pos[y]=pos[x];
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
last=z;
}
int t,ID[N],to[N][26];LL S[N];
inline void dfs1(Re x){
for(Re i=0;i<26;++i)
if(to[x][i])dfs1(to[x][i]),siz[x]+=siz[to[x][i]];
}
inline void dfs2(Re x){
if(x!=1)ID[++t]=x;
for(Re i=0;i<26;++i)if(to[x][i])dfs2(to[x][i]);
}
inline LL calc(Re L,Re R){return 1ll*(L+R)*(R-L+1)/2;}
inline void build(){
last=O=1;
for(Re i=1;i<=n/2;++i)swap(s[i],s[n-i+1]);
for(Re i=1;i<=n;++i)insert(s[i]-'a',i);
for(Re i=2;i<=O;++i)to[link[i]][s[pos[i]-maxlen[link[i]]]-'a']=i;
dfs1(1),dfs2(1);
for(Re i=1;i<=t;++i)x=ID[i],S[i]=S[i-1]+1ll*siz[x]*calc(maxlen[link[x]]+1,maxlen[x]);
}
inline char ask(LL K){
Re l=1,r=t,x;
while(l<r){
Re mid=l+r>>1;
if(S[mid]<K)l=mid+1;
else r=mid;
}
x=ID[l],K-=S[l-1],l=maxlen[link[x]]+1,r=maxlen[x];
while(l<r){
Re mid=l+r>>1;
if(1ll*siz[x]*calc(maxlen[link[x]]+1,mid)<K)l=mid+1;
else r=mid;
}
K-=1ll*siz[x]*calc(maxlen[link[x]]+1,l-1),K=(K-1)%l+1;
return s[pos[x]-K+1];
}
char ans;
inline void sakura(){
build();
while(T--)scanf("%lld%lld",&P,&M),K=P*G%M+1,G+=(ans=ask(K)),putchar(ans),puts("");
}
}T2;
int main(){
freopen("letter.in","r",stdin);
freopen("letter.out","w",stdout);
scanf("%s",s+1),n=strlen(s+1);in(T);
T2.sakura();
fclose(stdin);
fclose(stdout);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+5;
int n;char s[N];LL ans;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Suffix_Array{
int H[N],SA[N],rank[N],height[N];
inline void get_height(){
for(Re i=1;i<=n;++i)rank[SA[i]]=i;
for(Re i=1,k=0;i<=n;++i){
if(rank[i]==1)continue;
if(k)--k;
Re j=SA[rank[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
height[rank[i]]=H[i]=k;
}
}
}SA;
int pan[N<<1],pos[N<<1];
struct Suffix_Tree{
int t,tr[N<<1][26];
inline void add(Re x,Re y,Re c){tr[x][c]=y;}
inline void dfs(Re x){
if(pan[x])SA.SA[++t]=pos[x];
for(Re i=0;i<26;++i)if(tr[x][i])dfs(tr[x][i]);
}
}ST;
struct Suffix_Automaton{
int O,last,link[N<<1],maxlen[N<<1],trans[N<<1][26];
Suffix_Automaton(){last=O=1;}
inline void insert(Re ch,Re id){
Re z=++O,p=last;maxlen[z]=maxlen[p]+1,pan[z]=1,pos[z]=id;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
Re x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
pos[y]=pos[x],link[y]=link[x],link[x]=link[z]=y;
}
}
last=z;
}
inline void build(){
for(Re i=n;i>=1;--i)insert(s[i]-'a',i);
for(Re i=2;i<=O;++i)ST.add(link[i],i,s[pos[i]+maxlen[link[i]]]-'a');
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
in(n),scanf("%s",s+1),SAM.build(),ST.dfs(1),SA.get_height();
for(Re i=1;i<=n;++i)ans+=n-SA.SA[i]+1-SA.height[i];
printf("%lld\n",ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e6+3;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Suffix_Array{
int n,m,x[N],y[N],H[N],SA[N],cnt[N],rank[N],Height[N];char s[N];
//Suf[i]: s[i,n]
inline void get_SA(){
m=128;
for(Re i=1;i<=n;++i)++cnt[x[i]=s[i]];
for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
for(Re i=n;i>=1;--i)SA[cnt[x[i]]--]=i;
for(Re len=1;len<=n;len<<=1){
Re t=0;
for(Re i=n-len+1;i<=n;++i)y[++t]=i;
for(Re i=1;i<=n;++i)if(SA[i]>len)y[++t]=SA[i]-len;
for(Re i=1;i<=m;++i)cnt[i]=0;
for(Re i=1;i<=n;++i)++cnt[x[i]];
for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
for(Re i=n;i>=1;--i)SA[cnt[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[SA[1]]=m=1;
for(Re i=2;i<=n;++i)
x[SA[i]]=(y[SA[i]]==y[SA[i-1]]&&y[SA[i]+len]==y[SA[i-1]+len])?m:++m;
if(m==n)break;
}
for(Re i=1;i<=n;++i)printf("%d ",SA[i]);
}
inline void get_Height(){
for(Re i=1;i<=n;++i)rank[SA[i]]=i;
for(Re i=1,k=0;i<=n;++i){
if(rank[i]==1)continue;
if(k)--k;//H[i-1]-1<=H[i]
Re j=SA[rank[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
Height[rank[i]]=k;
}
// for(Re i=1;i<=n;++i)printf("%d ",Height[i]);
}
}SA;
int main(){
// freopen("123.txt","r",stdin);
scanf("%s",SA.s+1),SA.n=strlen(SA.s+1);
SA.get_SA(),SA.get_Height();
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5e5+5;
char s[N];
inline void in(Re &x){
Re f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Palindromic_Automaton{
int O,last,siz[N],cnt[N],len[N],fail[N],trans[N][26];
Palindromic_Automaton(){O=1,len[1]=-1,fail[0]=fail[1]=last=1;}
// 0:偶数回文的根节点
// 1:奇数回文的根节点
inline int find(Re p,Re id){while(s[id-1-len[p]]!=s[id])p=fail[p];return p;}
inline void insert(Re ch,Re id){
Re cur=find(last,id),now=trans[cur][ch];
if(!now){
now=++O,len[now]=len[cur]+2;
fail[now]=trans[find(fail[cur],id)][ch];
cnt[now]=cnt[fail[now]]+1;
trans[cur][ch]=now;
}
++siz[now],last=now;
}
inline void sakura(){
for(Re i=O;i>=2;--i)siz[fail[i]]+=siz[i];
}
}PAM;
int main(){
// freopen("123.txt","r",stdin);
scanf("%s",s+1);
for(Re i=1,k=0;s[i];++i){
s[i]=(s[i]-'a'+k)%26+'a';
PAM.insert(s[i]-'a',i);
printf("%d ",k=PAM.cnt[PAM.last]);
}
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5;
int n;char ch[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Suffix_Automaton{
int O,link[N],maxlen[N],trans[N][26];
//trans[i]: 状态转移指针
Suffix_Automaton(){O=1;}
inline int insert(Re ch,Re last){
if(trans[last][ch]){
Re p=last,x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])return x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[x]=y;
return y;
}
}
Re z=++O,p=last;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
Re x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return z;
}
inline void sakura(){
LL ans=0;
for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
printf("%lld\n",ans);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
in(n);
for(Re i=1;i<=n;++i){
scanf("%s",ch+1);Re last=1;
for(Re j=1;ch[j];++j)last=SAM.insert(ch[j]-'a',last);
}
SAM.sakura();
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5,M=1e6+3;
int n,t;char ch[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Trie{
int O,c[M],fa[M],tr[M][26];
Trie(){O=1;}
inline void insert(char ch[]){
Re p=1;
for(Re i=1;ch[i];++i){
Re a=ch[i]-'a';
if(!tr[p][a])tr[p][a]=++O,fa[O]=p,c[O]=a;
p=tr[p][a];
}
}
}T1;
struct Suffix_Automaton{
int O,pos[N],link[N],maxlen[N],trans[N][26];queue<int>Q;
//trans[i]: 状态转移指针
Suffix_Automaton(){O=1;}
inline int insert(Re ch,Re last){
Re x,y,z=++O,p=last;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return z;
}
inline void build(){
for(Re i=0;i<26;++i)if(T1.tr[1][i])Q.push(T1.tr[1][i]);
pos[1]=1;
while(!Q.empty()){
Re x=Q.front();Q.pop();
pos[x]=insert(T1.c[x],pos[T1.fa[x]]);
for(Re i=0;i<26;++i)if(T1.tr[x][i])Q.push(T1.tr[x][i]);
}
}
inline void sakura(){
LL ans=0;
for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
printf("%lld\n",ans);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
in(n);
for(Re i=1;i<=n;++i)scanf("%s",ch+1),T1.insert(ch);
SAM.build(),SAM.sakura();
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=2e6+5,M=1e6+3;
int n,t;char ch[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Trie{
int O,c[M],fa[M],tr[M][26];
Trie(){O=1;}
inline void insert(char ch[]){
Re p=1;
for(Re i=1;ch[i];++i){
Re a=ch[i]-'a';
if(!tr[p][a])tr[p][a]=++O,fa[O]=p,c[O]=a;
p=tr[p][a];
}
}
}T1;
struct Suffix_Automaton{
int O,pos[N],link[N],maxlen[N],trans[N][26];queue<int>Q;
//trans[i]: 状态转移指针
Suffix_Automaton(){O=1;}
inline int insert(Re ch,Re last){
Re x,y,z=++O,p=last;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return z;
}
inline void dfs(Re x){
for(Re i=0,to;i<26;++i)if(to=T1.tr[x][i])
pos[to]=insert(T1.c[to],pos[x]),dfs(to);
}
inline void build(){pos[1]=1,dfs(1);}
inline void sakura(){
LL ans=0;
for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
printf("%lld\n",ans);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
in(n);
for(Re i=1;i<=n;++i)scanf("%s",ch+1),T1.insert(ch);
SAM.build(),SAM.sakura();
}
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,M=5e4+3,logN=21;
int n,m,x,y,l,r,T,pos[N];char s[N],ch[M];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct QWQ{
int x,id;QWQ(Re X=0,Re ID=0){x=X,id=ID;}
inline bool operator>(const QWQ &O)const{return x!=O.x?x>O.x:id<O.id;}
};
inline QWQ max(QWQ A,QWQ B){return A>B?A:B;}
int pt[N+M<<1];
struct Segment_Tree{
#define pl (tr[p].lp)
#define pr (tr[p].rp)
#define mid ((L+R)>>1)
int O;
struct QAQ{int lp,rp;QWQ ans;}tr[(M<<1)*30];
inline void pushup(Re p){
tr[p].ans=max(tr[pl].ans,tr[pr].ans);
}
inline void change(Re &p,Re L,Re R,Re x){
if(!p)p=++O;
if(L==R){++tr[p].ans.x,tr[p].ans.id=L;return;}
if(x<=mid)change(pl,L,mid,x);
else change(pr,mid+1,R,x);
pushup(p);
}
inline int merge(Re p,Re q,Re L,Re R){
if(!p||!q)return p+q;
Re x=++O;
if(L==R){tr[x]=tr[p],tr[x].ans.x+=tr[q].ans.x;return x;}
tr[x].lp=merge(pl,tr[q].lp,L,mid);
tr[x].rp=merge(pr,tr[q].rp,mid+1,R);
pushup(x);return x;
}
inline QWQ ask(Re p,Re L,Re R,Re l,Re r){
if(!p)return QWQ(0,m+1);
if(l<=L&&R<=r)return tr[p].ans;
QWQ ans=QWQ(0,m+1);
if(l<=mid)ans=max(ans,ask(pl,L,mid,l,r));
if(r>mid)ans=max(ans,ask(pr,mid+1,R,l,r));
return ans;
}
}TR;
struct Suffix_Automaton{
int O,link[N+M<<1],maxlen[N+M<<1],trans[N+M<<1][26];
Suffix_Automaton(){O=1;}
inline int insert(Re ch,Re last,Re id){
if(trans[last][ch]){
Re p=last,x=trans[p][ch];
if(maxlen[p]+1==maxlen[x]){if(id)TR.change(pt[x],1,m,id);return x;}
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[x]=y;
if(id)TR.change(pt[y],1,m,id);
return y;
}
}
Re z=++O,p=last;maxlen[z]=maxlen[p]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
Re x=trans[p][ch];
if(maxlen[x]==maxlen[p]+1)link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[x]=link[z]=y;
}
}
if(id)TR.change(pt[z],1,m,id);
return z;
}
int o,deep[N+M<<1],head[N+M<<1],ant[N+M<<1][23];
struct QAQ{int to,next;}a[N+M<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void dfs(Re x,Re fa){
deep[x]=deep[ant[x][0]=fa]+1;
for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
for(Re i=head[x],to;i;i=a[i].next)
dfs(to=a[i].to,x),pt[x]=TR.merge(pt[x],pt[to],1,m);
}
inline void build(){
for(Re i=2;i<=O;++i)add(link[i],i);dfs(1,0);
}
inline int get(Re x,Re len){
Re p=pos[x];
for(Re i=logN;i>=0;--i)if(ant[p][i]&&maxlen[ant[p][i]]>=len)p=ant[p][i];
return p;
}
inline void sakura(Re l,Re r,Re x,Re y){
QWQ ans=TR.ask(pt[get(y,y-x+1)],1,m,l,r);
if(ans.x==0)ans.id=l;
printf("%d %d\n",ans.id,ans.x);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
scanf("%s",s+1),n=strlen(s+1),in(m);
for(Re i=1;i<=m;++i){
scanf("%s",ch+1);Re last=1;
for(Re j=1;ch[j];++j)last=SAM.insert(ch[j]-'a',last,i);
}
for(Re i=1,last=1;i<=n;++i)pos[i]=last=SAM.insert(s[i]-'a',last,0);
SAM.build(),in(T);
while(T--)in(l),in(r),in(x),in(y),SAM.sakura(l,r,x,y);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=2e5+3;
int n,T;LL Ans[M];char s[N];
struct Query{int l,r,id;inline bool operator<(const Query &O)const{return r<O.r;}}Q[M];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{LL S,add;}tr[N<<2];
inline void updata(Re p,Re L,Re R,LL v){tr[p].add+=v,tr[p].S+=v*(R-L+1);}
inline void pushdown(Re p,Re L,Re R){
if(tr[p].add)updata(pl,L,mid,tr[p].add),updata(pr,mid+1,R,tr[p].add),tr[p].add=0;
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
if(l<=L&&R<=r){updata(p,L,R,v);return;}
pushdown(p,L,R);
if(l<=mid)change(pl,L,mid,l,r,v);
if(r>mid)change(pr,mid+1,R,l,r,v);
tr[p].S=tr[pl].S+tr[pr].S;
}
inline LL ask(Re p,Re L,Re R,Re l,Re r){
if(l<=L&&R<=r)return tr[p].S;
pushdown(p,L,R);LL ans=0;
if(l<=mid)ans+=ask(pl,L,mid,l,r);
if(r>mid)ans+=ask(pr,mid+1,R,l,r);
return ans;
}
#undef pl
#undef pr
}TR;
struct Suffix_Automaton{
int O,last,pos[N],link[N<<1],maxlen[N<<1],trans[N<<1][26];
Suffix_Automaton(){last=O=1;}
inline void insert(Re ch,Re id){
Re z=++O,p=last;maxlen[z]=maxlen[p]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
Re x=trans[p][ch];
if(maxlen[x]==maxlen[p]+1)link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
pos[id]=last=z;
}
}SAM;
struct Link_Cut_Tree{
#define pl (tr[p].ps[0])
#define pr (tr[p].ps[1])
#define pf (tr[p].fa)
#define pv (tr[p].v)
int Q[N<<1];
struct QAQ{int v,fa,tag,ps[2];}tr[N<<1];
inline void updata(Re p,Re v){tr[p].tag=tr[p].v=v;}
inline void pushdown(Re p){
if(tr[p].tag){
if(pl)updata(pl,tr[p].tag);
if(pr)updata(pr,tr[p].tag);
tr[p].tag=0;
}
}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
inline void rotate(Re p){
Re fa=pf,fas=which(p);
Re pa=tr[fa].fa,pas=which(fa);
Re x=tr[p].ps[fas^1];
if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
connect(x,fa,fas),connect(fa,p,fas^1);
}
inline void splay(Re p){
Re x=p,t=0;Q[++t]=x;
while(tr[x].fa)Q[++t]=x=tr[x].fa;
while(t)pushdown(Q[t--]);
for(Re fa;nort(p);rotate(p))
if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
}
inline void access(Re p,Re r){
Re son=0;
for(;p;son=p,p=pf){
splay(p);
if(pv)TR.change(1,1,n,pv-SAM.maxlen[p]+1,pv-SAM.maxlen[pf],-1);
pr=son;
}
updata(son,r),TR.change(1,1,n,1,r,1);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
scanf("%s",s+1),n=strlen(s+1),in(T);
for(Re i=1;i<=n;++i)SAM.insert(s[i]-'a',i);
for(Re i=2;i<=SAM.O;++i)T1.tr[i].fa=SAM.link[i];
for(Re i=1;i<=T;++i)in(Q[i].l),in(Q[i].r),Q[i].id=i;
sort(Q+1,Q+T+1);
for(Re i=1,r=0;i<=T;++i){
while(r<Q[i].r)++r,T1.access(SAM.pos[r],r);
Ans[Q[i].id]=TR.ask(1,1,n,Q[i].l,Q[i].r);
}
for(Re i=1;i<=T;++i)printf("%lld\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#define Re register int
#define LL long long
using namespace std;
const int N=2e5+5;
int n,t,T,x,s[N],ch[N],Len[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Suffix_Automaton{
int O,pos[N],cnt[N],link[N],maxlen[N],minlen[N];queue<int>Q;map<int,int>trans[N];
Suffix_Automaton(){O=1;}
inline int insert(Re ch,Re last){
if(trans[last][ch]&&maxlen[last]+1==maxlen[trans[last][ch]])return trans[last][ch];
Re x,y,z=++O,p=last,flag=0;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
if(maxlen[p]+1==maxlen[z])flag=1;
y=++O;maxlen[y]=maxlen[p]+1;
trans[y]=trans[x];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return flag?y:z;
}
int co[N];
inline void updata(Re p,Re id){
while(p&&co[p]!=id)++cnt[p],co[p]=id,p=link[p];
}
int gs[N],Ans[N];
inline void updata_(Re p,Re id){
while(p&&co[p]!=id)Ans[id]+=gs[p],co[p]=id,p=link[p];
}
inline void ask(Re ch[],Re L){
Re p=1,flag=1;
for(Re i=1;i<=L&&flag;++i){
Re a=ch[i];
if(trans[p][a])p=trans[p][a];
else flag=0;
}
if(flag)++gs[p];
printf("%d\n",flag?cnt[p]:0);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T);
for(Re i=1;i<=n;++i){
in(Len[(i<<1)-1]);Re last=1;
for(Re j=1;j<=Len[(i<<1)-1];++j)in(x),last=SAM.insert(s[++t]=x,last);
in(Len[i<<1]);last=1;
for(Re j=1;j<=Len[i<<1];++j)in(x),last=SAM.insert(s[++t]=x,last);
}
for(Re i=1,t=0;i<=n;++i){
for(Re j=1,p=1;j<=Len[(i<<1)-1];++j)
SAM.updata(p=SAM.trans[p][s[++t]],i);
for(Re j=1,p=1;j<=Len[i<<1];++j)
SAM.updata(p=SAM.trans[p][s[++t]],i);
}
while(T--){
in(Len[0]);
for(Re i=1;i<=Len[0];++i)in(ch[i]);
SAM.ask(ch,Len[0]);
}
memset(SAM.co,0,sizeof(SAM.co));
for(Re i=1,t=0;i<=n;++i){
for(Re j=1,p=1;j<=Len[(i<<1)-1];++j)
SAM.updata_(p=SAM.trans[p][s[++t]],i);
for(Re j=1,p=1;j<=Len[i<<1];++j)
SAM.updata_(p=SAM.trans[p][s[++t]],i);
}
for(Re i=1;i<=n;++i)printf("%d ",SAM.Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=6e5+5,logN=19;
char s[N>>1];
inline void in(Re &x){
Re f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Suffix_Automaton{
int O,last,pos[N],siz[N],link[N],maxlen[N],trans[N][26];LL ans;
Suffix_Automaton(){last=O=1;}
inline void insert(Re ch){
Re z=++O,p=last;siz[z]=1,maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
Re x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[x]=link[z]=y;
}
}
last=z;
}
int o,deep[N],head[N],ant[N][20];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void dfs(Re x,Re fa){
deep[x]=deep[ant[x][0]=fa]+1;
for(Re j=1;(1<<j)<=deep[x];++j)ant[x][j]=ant[ant[x][j-1]][j-1];
for(Re i=head[x];i;i=a[i].next)dfs(a[i].to,x),siz[x]+=siz[a[i].to];
}
inline void build(){
for(Re i=1;s[i];++i)insert(s[i]-'a'),pos[i]=last;
for(Re i=2;i<=O;++i)add(link[i],i);
dfs(1,0);
}
inline void check(Re x,Re len){
Re p=pos[x+len-1];
for(Re i=logN;i>=0;--i)
if(maxlen[ant[p][i]]>=len)p=ant[p][i];
ans=max(ans,(LL)len*siz[p]);
}
int m,r[N];char b[N];
inline void sakura(){
build();
b[m=0]='$',b[++m]='|';
for(Re i=1;s[i];++i)b[++m]=s[i],b[++m]='|';
for(Re i=1,R=0,mid=0;i<=m;++i){
r[i]=i<=R?min(r[(mid<<1)-i],R-i+1):1;
while(b[i-r[i]]==b[i+r[i]]){
++r[i];
if(i+r[i]-1>R)check(i-r[i]+1+1>>1,r[i]-!(i+r[i]&1));
}
if(i+r[i]-1>R)mid=i,R=i+r[i]-1;
}
printf("%lld\n",ans);
}
}SAM;
int main(){
freopen("123.txt","r",stdin);
scanf("%s",s+1),SAM.sakura();
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+5;
char s[N];
inline void in(Re &x){
Re f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Palindromic_Automaton{
int O,last,siz[N],len[N],fail[N],trans[N][26];
Palindromic_Automaton(){O=1,len[1]=-1,fail[0]=fail[1]=last=1;}
inline int find(Re p,Re id){while(s[id-1-len[p]]!=s[id])p=fail[p];return p;}
inline void insert(Re ch,Re id){
Re cur=find(last,id),now=trans[cur][ch];
if(!now){
now=++O,len[now]=len[cur]+2;
fail[now]=trans[find(fail[cur],id)][ch];
trans[cur][ch]=now;
}
++siz[now],last=now;
}
inline void sakura(){
LL ans=0;
for(Re i=O;i>=2;--i)siz[fail[i]]+=siz[i],ans=max(ans,(LL)siz[i]*len[i]);
printf("%lld\n",ans);
}
}PAM;
int main(){
// freopen("123.txt","r",stdin);
scanf("%s",s+1);
for(Re i=1;s[i];++i)PAM.insert(s[i]-'a',i);
PAM.sakura();
}
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=8e5+5;
char ch[200003];LL ans;
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct Suffix_Automaton{
int O,ru[N],link[N],maxlen[N],siz[N][2],trans[N][26];queue<int>Q;
// siz[x]: |endpos[x]| 节点x的endpos大小
Suffix_Automaton(){O=1;}
inline int insert(Re ch,Re last,Re id){
if(trans[last][ch]){
Re p=last,x=trans[p][ch];
if(maxlen[p]+1==maxlen[x]){siz[x][id]=1;return x;}
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[x]=y;
siz[y][id]=1;return y;
}
}
Re z=++O,p=last;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
Re x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
siz[z][id]=1;
return z;
}
inline void sakura(){
for(Re i=2;i<=O;++i)++ru[link[i]];
for(Re i=1;i<=O;++i)if(!ru[i])Q.push(i);
while(!Q.empty()){
Re x=Q.front();Q.pop();
siz[link[x]][0]+=siz[x][0];
siz[link[x]][1]+=siz[x][1];
if(!(--ru[link[x]]))Q.push(link[x]);
}
for(Re i=2;i<=O;++i)//ͳ�ƴ�
ans+=(LL)siz[i][0]*siz[i][1]*(maxlen[i]-maxlen[link[i]]);
printf("%lld\n",ans);
}
}SAM;
int main(){
// freopen("123.txt","r",stdin);
for(Re i=0;i<2;++i){
scanf("%s",ch+1);Re last=1;
for(Re j=1;ch[j];++j)last=SAM.insert(ch[j]-'a',last,i);
}
SAM.sakura();
}