Brief description:
设两个字符串的最长公共前缀和后缀的长度分别为 $$a$$, $$b$$。
则它们相似程度，定义为 $$a^2 + b^2$$。
给定一个字符串，每次询问其字典序第 k1-th 大和第 k2-th 大的两个子串间的相似程度。
Analysis:
求一个字符串的字典序第 k-th 大子串可以用 SA 做到每次询问log(n)。
方法是，在搞出高度函数的时候，顺便开一个数组记录到 SA 中的的某个为止，共会出现多少子串。每次询问直接在这个数组上二分即可。
（Open Problem: 这里我们只需要输出子串的左右下标，类似对于 Rank 我们给出子串的下标，同样 SA 可以用类似方法在 log(n) 时间内解决问题。对于 Select 以及 Rank，用 SAM 是否也可以达到 log(n) 的复杂度？。
之后就是 lcp 了。。。（这题我用 hash 求 lcp 挂了。。= =）。
https://gist.github.com/lychees/7079186
const int N = int(1e5)+9, M = 26+1, LV = 20;
LL a[N]; char s[N]; int n;
int C[N], key[N], t1[N], t2[N];
struct SA{
int a[3*N], sa[3*N], rk[N], h[N];
inline void rs(int*x,int*y,int*sa,int n,int m){
REP(i, n)key[i]=i[y][x];
memset(C, 0,sizeof(C[0])*m);
REP(i, n) ++C[key[i]];
FOR(i, 1, m) C[i] += C[i-1];
DWN(i, n, 0) sa[--C[key[i]]] = y[i];
}
void da(int*a,int*sa,int n,int m){
int *x = t1, *y = t2;
memset(C,0,sizeof(C[0])*m);
REP(i, n)++C[x[i]=a[i]];
FOR(i, 1, m)C[i]+=C[i-1];
DWN(i, n, 0)sa[--C[x[i]]]=i;
for(int l=1,p=1;p<n;l<<=1,m=p){
p=0; FOR(i, n-l, n) y[p++]=i;
REP(i, n) if (sa[i]>=l) y[p++]=sa[i]-l;
rs(x,y,sa,n,m),swap(x,y),x[sa[0]]=p=0;FOR(i, 1, n)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+l]==y[sa[i-1]+l])?p:++p;
++p;
}
}
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int c0(int*r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k,int*r,int a,int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
else return r[a]<r[b]||r[a]==r[b]&&key[a+1]<key[b+1];}
void dc3(int*a,int*sa,int n,int m){
int i, j, *an=a+n, *san=sa+n, ta=0, tb=(n+1)/3, tbc=0, p;
a[n] = a[n+1] = 0; REP(i, n) if (i%3) t1[tbc++]=i;
rs(a+2,t1,t2,tbc,m),rs(a+1,t2,t1,tbc,m),rs(a,t1,t2,tbc,m);
p=0,an[F(t2[0])]=0;FOR(i, 1, tbc)
an[F(t2[i])]=c0(a,t2[i-1],t2[i])?p:++p;
if (++p < tbc) dc3(an,san,tbc,p);
else REP(i, tbc) san[an[i]] = i;
REP(i, tbc) if(san[i] < tb) t2[ta++] = san[i] * 3;
if (n%3==1) t2[ta++] = n-1; rs(a,t2,t1,ta,m);
REP(i, tbc) key[t2[i]=G(san[i])] = i;
for(i=0,j=0,p=0; i<ta && j<tbc; p++)
sa[p]=c12(t2[j]%3,a,t1[i],t2[j]) ? t1[i++] : t2[j++];
for(;i<ta;p++) sa[p]=t1[i++]; for(;j<tbc;p++) sa[p]=t2[j++];
}
void get_h(){
REP_1(i, n) rk[sa[i]] = i;
int k=0;for(int i=0;i<n;h[rk[i++]]=k){
if (k)--k;for(int j=sa[rk[i]-1];a[i+k]==a[j+k];++k);
}
}
int ST[LV][N];
#define cmp(a, b) (h[a]<h[b]?a:b)
inline int lcp(int l, int r){
int lv = lg2(r - l); ++l, ++r;
return min(h[ST[lv][l]], h[ST[lv][r-_1(lv)]]);
}
inline int lcpp(int l, int r){
if (l == r) return n-l;
l = rk[l], r = rk[r]; if (l > r) swap(l, r);
return lcp(l, r);
}
void get_lcp(){
REP_1(i, n) ST[0][i] = i;
for (int lv = 1; _1(lv) <= n; ++lv){
for (int i = 1; i + _1(lv) <= n + 1; ++i)
ST[lv][i] = cmp(ST[lv-1][i], ST[lv-1][i+_1(lv-1)]);
}
}
void bd(){
dc3(a,sa,n+1,M),get_h(),get_lcp();
}
} A, B;
PII get(LL k){
int r = lower_bound(a, a+n, k) - a; k -= a[r-1];
return MP(A.sa[r]+1, A.h[r]+k);
}
LL f(LL x, LL y){
if (x>a[n] || y>a[n]) return -1;
PII a = get(x), b = get(y); int t = min(a.se, b.se);
return sqr(LL(min(t,A.lcpp(a.fi-1, b.fi-1)))) + sqr(LL(min(t,B.lcpp(n-(a.fi+a.se-1), n-(b.fi+b.se-1)))));
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int m; RD(n, m); strlen(RS(s)); REP(i, n) B.a[n-i-1]=A.a[i]=s[i]-='a'-1;
A.bd(); B.bd(); REP_1(i, n) a[i]=a[i-1]+n-A.sa[i]-A.h[i];
DO(m) OT(f(RD(), RD()));
}
