输入第1行，包含3个整数N，Q。Q代表询问组数。
第2行是字符串S。
接下来Q行，每行两个整数i和j。（1≤i≤j）。

输出共Q行，每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串，则输出-1。

5 3
ababa
3 5
5 9
8 10

18
16
-1

样例解释

第1组询问：两个子串是“aba”,“ababa”。f = 32 + 32 = 18。

第2组询问：两个子串是“ababa”,“baba”。f = 02 + 42 = 16。

第3组询问：不存在第10个子串。输出-1。

数据范围

N≤100000，Q≤100000，字符串只由小写字母'a'~'z'组成

后缀数组+二分+RMQ

 #include <bits/stdc++.h>

 template <class T>

 T sqr(T x)

 {

     return x*x;

 }

 typedef long long longint;

 const int maxn = ;

 const longint inf = 1e9;

 int n, m;

 char s[maxn];

 longint g[maxn];

 longint pre[maxn];

 class SuffixArray

 {

 public:

     int sa[maxn], rk[maxn], ht[maxn];

     inline void init(void)

     {

         memset(ca, , sizeof(ca));

         for (int i = ; i <= n; ++i)

             ++ca[s[i]];

         for (int i = ; i <= ; ++i)

             ca[i] += ca[i - ];

         for (int i = n; i >= ; --i)

             sa[ca[s[i]]--] = i;

         rk[sa[]] = ;

         for (int i = ; i <= n; ++i)

             rk[sa[i]] = rk[sa[i - ]] + (s[sa[i]] != s[sa[i - ]]);

         for (int l = ; rk[sa[n]] < n; l <<= )

         {

             memset(ca, , sizeof(ca));

             memset(cb, , sizeof(cb));

             for (int i = ; i <= n; ++i)

             {

                 ++ca[wa[i] = rk[i]];

                 ++cb[wb[i] = i + l <= n ? rk[i + l] :];

             }

             for (int i = ; i <= n; ++i)

             {

                 ca[i] += ca[i - ];

                 cb[i] += cb[i - ];

             }

             for (int i = n; i >= ; --i)

                 ta[cb[wb[i]]--] = i;

             for (int i = n; i >= ; --i)

                 sa[ca[wa[ta[i]]]--] = ta[i];

             rk[sa[]] = ;

             for (int i = ; i <= n; ++i)

                 rk[sa[i]] = rk[sa[i - ]] + (wa[sa[i]] != wa[sa[i - ]] || wb[sa[i]] != wb[sa[i - ]]);

         }

         for (int i = , j = ; i <= n; ++i)

         {

             if (--j < )j = ;

             while (s[i + j] == s[sa[rk[i] - ] + j])++j;

             ht[rk[i]] = j;

         }

         build(, , n);

     }

     inline int lcp(int a, int b)

     {

         a = rk[a];

         b = rk[b];

         if (a > b)

         {

             a ^= b;

             b ^= a;

             a ^= b;

         }

         return query(, , n, a + , b);

     }

 private:

     void build(int t, int l, int r)

     {

         if (l == r)

             tr[t] = ht[l];

         else

         {

             int mid = (l + r) >> ;

             build(t << , l, mid);

             build(t <<  | , mid + , r);

             tr[t] = std::min(tr[t << ], tr[t <<  | ]);

         }

     }

     int query(int t, int l, int r, int a, int b)

     {

         if (l == a && r == b)

             return tr[t];

         else

         {

             int mid = (l + r) >> ;

             if (b <= mid)

                 return query(t << , l, mid, a, b);

             else if (a > mid)

                 return query(t <<  | , mid + , r, a, b);

             else

                 return std::min(query(t << , l, mid, a, mid), query(t <<  | , mid + , r, mid + , b));

         }

     }

     int ta[maxn], wa[maxn], wb[maxn], ca[maxn], cb[maxn], tr[maxn << ];

 }A, B;

 signed main(void)

 {

     scanf("%d%d%s", &n, &m, s + ); 

     g[] = -;

     for (int i = ; i <= n; ++i)

         g[i] = g[i >> ] + ;

     A.init();

     std::reverse(s + , s +  +n);

     B.init();

     pre[] = ;

     for (int i = ; i <= n; ++i)

         pre[i] = pre[i - ] + n - A.sa[i] +  - A.ht[i];

     for (int i = ; i <= m; ++i)

     {

         longint lt, rt; scanf("%lld%lld", &lt, &rt);

         if (lt > pre[n] || rt > pre[n])

             { puts("-1"); continue; }

         int id1, id2, a1, b1, a2, b2;

         id1 = std::lower_bound(pre + , pre +  + n, lt) - pre;

         id2 = std::lower_bound(pre + , pre +  + n, rt) - pre;

         a1 = A.sa[id1];

         a2 = A.sa[id2];

         b1 = a1 + A.ht[id1] -  + lt - pre[id1 - ];

         b2 = a2 + A.ht[id2] -  + rt - pre[id2 - ];

         longint ans = , tmp;

         tmp = a1 == a2 ? inf : A.lcp(a1, a2);

         tmp = std::min(tmp, (longint)std::min(b1 - a1 + , b2 - a2 + ));

         ans += sqr(tmp);

         tmp = b1 == b2 ? inf : B.lcp(n - b1 + , n - b2 + );

         tmp = std::min(tmp, (longint)std::min(b1 - a1 + , b2 - a2 + ));

         ans += sqr(tmp);

         printf("%lld\n", ans);

     }

 }