//GET H
for( int 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 = sa[ra[i]], mx = max( p, q );
while( mx+h[i] < n && a[p+h[i]] == a[q+h[i]] ) h[i]++;
}
//GET height
for( int i = 0 ; i < n ; i++ ) he[ra[i]] = h[i];
//GET Sparse_Table
for( int i = 0 ; i < n ; i++ ) st[0][i] = he[i];
for( int l = 1 ; l < 15 ; l++ ){
int L = 1<<l;
for( int i = 0 ; i < n-L+1 ; i++ )
st[l][i] = min( st[l-1][i], st[l-1][i+L/2] );
}
//LCP(O(1)RMQ)
int LCP( int l, int r ){
if( l == r ) return n-sa[l];
if( l > r ) swap( l, r ); l++;
int L = __lg(r-l+1);
return min( st[L][l], st[L][r-(1<<L)+1] );
}