int *rk = new int[N], *kr = new int[N], cnt[N];
void SA( int sa[], int ra[], char s[] ){
int n = strlen(s), m = 128, l, h, i, j;
for( i=j=0; i<=n; i++ ) rk[i]=s[sa[i]=i];
for( l=1,h=0; j<=n; l<<=1 ){
for( i=n-h,j=0; i<n; i++ ) kr[j++]=i;
for( i=0; i<n; i++ ) if( sa[i]>=h ) kr[j++]=sa[i]-h;
for( i=0; i<m; i++ ) cnt[i]=0;
for( i=0; i<n; i++ ) cnt[rk[i]]++;
for( i=1; i<m; i++ ) cnt[i]+=cnt[i-1];
for( i=n-1; i>=0; i-- ) sa[--cnt[rk[kr[i]]]] =kr[i];
for( i=0,j=1; i<n; i++ ) kr[sa[i]]=(rk[sa[i]]==rk[sa[i+1]]&&rk[sa[i]+h]==rk[sa[i+1]+h])?j:j++;
h=l; m=j; swap( rk, kr );
}for( i=0; i<n; i++ ) ra[sa[i]]=i;
}
int sa[N], ra[N], h[N], spa[30][N];
void INIT( char s[] ){
int n=strlen(s), i, j, l;
SA( sa, ra, s );
for( i=0; i<n; i++ ){
if( ra[i]==0 ){ h[i]=0; continue; }
h[i]=(i==0||h[i-1]<=1)?0:h[i-1]-1;
int p=sa[ra[i]-1], q=i, mx=p; if(mx<q)mx=q;
while( mx+h[i]<n && s[p+h[i]]==s[q+h[i]] )h[i]++;
}for( i=0; i<n; i++ ) spa[0][i]=h[sa[i]];
for( i=1; i<23; i++ ) for( j=0,l=1<<i; j<n-l+1; j++ ) spa[i][j]=min(spa[i-1][j],spa[i-1][j+l/2]);
}
int LCP( int i, int j ){
if( i>j ) swap(i,j); i++;int l = __lg(j-i+1);
return min( spa[l][i], spa[l][j-(1<<l)+1] );
}