基础板子

namespace SA{
    int x[400010],y[400010],SA[400010],rk[400010],ht[400010],t[400010];
    int st[19][400010],lg[400010];
    il int getLCP(int x,int y){
        if(x==y)return 1e9;
        int l=lg[y-x];
        return std::min(st[l][x],st[l][y-(1<<l)]);
    }
    il vd getSA(){
        int set=400000;
        for(int i=1;i<=N;++i)++t[x[i]=S[i]];
        for(int i=1;i<=set;++i)t[i]+=t[i-1];
        for(int i=N;i;--i)SA[t[x[i]]--]=i;
        for(int k=1;k<=N;k<<=1){
            int p=0;
            for(int i=N-k+1;i<=N;++i)y[++p]=i;
            for(int i=1;i<=N;++i)if(SA[i]>k)y[++p]=SA[i]-k;
            for(int i=1;i<=set;++i)t[i]=0;
            for(int i=1;i<=N;++i)++t[x[y[i]]];
            for(int i=1;i<=set;++i)t[i]+=t[i-1];
            for(int i=N;i;--i)SA[t[x[y[i]]]--]=y[i];
            std::swap(x,y);x[SA[1]]=p=1;
            for(int i=2;i<=N;++i){
                if(y[SA[i]]!=y[SA[i-1]]||y[SA[i]+k]!=y[SA[i-1]+k])++p;
                x[SA[i]]=p;
            }
            if(p>=N)break;set=p;
        }
        for(int i=1;i<=N;++i)rk[SA[i]]=i;
        for(int i=1,j,k;i<=N;++i){
            if(rk[i]==N)continue;
            if(k)--k;
            j=SA[rk[i]+1];
            while(S[i+k]==S[j+k])++k;
            ht[rk[i]]=k;
        }
        for(int i=2;i<=N;++i)lg[i]=lg[i>>1]+1;
        for(int i=1;i<=N;++i)st[0][i]=ht[i];
        for(int i=1;i<=lg[N];++i)
            for(int j=1;j+(1<<i)-1<=N;++j)
                st[i][j]=std::min(st[i-1][j],st[i-1][j+(1<<i-1)]);
    }
}namespace SA{
    int x[400010],y[400010