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

5 3
ababa
3 5
5 9
8 10

18
16
-1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;
#define LL long long

LL read() {
	LL x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
	return x * f;
}

#define maxn 100010
#define maxlog 17

int Log[maxn];

struct Suf {
	char S[maxn];
	int n, rank[maxn], height[maxn], sa[maxn], Ws[maxn], mnh[maxlog][maxn];
	
	void init(const char* Str) {
		strcpy(S + 1, Str);
		n = strlen(S + 1);
		return ;
	}
	
	bool cmp(int* a, int p1, int p2, int l) {
		if(p1 + l > n && p2 + l > n) return a[p1] == a[p2];
		if(p1 + l > n || p2 + l > n) return 0;
		return a[p1] == a[p2] && a[p1+l] == a[p2+l];
	}
	void ssort() {
		int *x = rank, *y = height;
		int m = 0;
		for(int i = 1; i <= n; i++) Ws[x[i] = S[i]]++, m = max(m, x[i]);
		for(int i = 1; i <= m; i++) Ws[i] += Ws[i-1];
		for(int i = n; i; i--) sa[Ws[x[i]]--] = i;
		for(int j = 1, pos = 0; pos < n; j <<= 1, m = pos) {
			pos = 0;
			for(int i = n - j + 1; i <= n; i++) y[++pos] = i;
			for(int i = 1; i <= n; i++) if(sa[i] > j) y[++pos] = sa[i] - j;
			for(int i = 1; i <= m; i++) Ws[i] = 0;
			for(int i = 1; i <= n; i++) Ws[x[i]]++;
			for(int i = 1; i <= m; i++) Ws[i] += Ws[i-1];
			for(int i = n; i; i--) sa[Ws[x[y[i]]]--] = y[i];
			swap(x, y); pos = 1; x[sa[1]] = 1;
			for(int i = 2; i <= n; i++) x[sa[i]] = cmp(y, sa[i], sa[i-1], j) ? pos : ++pos;
		}
		return ;
	}
	void calch() {
		for(int i = 1; i <= n; i++) rank[sa[i]] = i;
		for(int i = 1, j, k = 0; i <= n; height[rank[i++]] = k)
			for(k ? k-- : 0, j = sa[rank[i]-1]; S[j+k] == S[i+k]; k++);
		return ;
	}
	
	void rmq_init() {
		Log[1] = 0;
		for(int i = 2; i <= n; i++) Log[i] = Log[i>>1] + 1;
		for(int i = 1; i <= n; i++) mnh[0][i] = height[i];
		for(int j = 1; (1 << j) <= n; j++)
			for(int i = 1; i + (1 << j) - 1 <= n; i++)
				mnh[j][i] = min(mnh[j-1][i], mnh[j-1][i+(1<<j-1)]);
		return ;
	}
	int que(int l, int r) {
		if(l > r) swap(l, r);
		if(l == r) return n - sa[l] + 1;
		l++;
		int t = Log[r-l+1];
		return min(mnh[t][l], mnh[t][r-(1<<t)+1]);
	}
} sol1, sol2;

char inS[maxn];
LL en[maxn];

int rev(int x) { return sol2.rank[sol1.n-sol1.sa[x]+1]; }

int main() {
	int n = read(), q = read();
	scanf("%s", inS);
	sol1.init(inS);
	for(int i = 0; i < (sol1.n >> 1); i++) swap(inS[i], inS[sol1.n-i-1]);
	sol2.init(inS);
	
	sol1.ssort(); sol1.calch(); sol1.rmq_init();
	sol2.ssort(); sol2.calch(); sol2.rmq_init();
	for(int i = 1; i <= n; i++) en[i] = n - sol1.sa[i] + 1 - sol1.height[i];
	for(int i = 1; i <= n; i++) en[i] += en[i-1];
//	for(int i = 1; i <= n; i++) printf("%lld%c", en[i], i < n ? ‘ ‘ : ‘\n‘);
	while(q--) {
		LL l = read(), r = read();
		if(l > en[n] || r > en[n]){ puts("-1"); continue; }
		int prel = lower_bound(en + 1, en + n + 1, l) - en,
			prer = lower_bound(en + 1, en + n + 1, r) - en,
			lenl = n - sol1.sa[prel] + 1 - (en[prel] - l),
			lenr = n - sol1.sa[prer] + 1 - (en[prer] - r);
//		printf("%d %d [%d %d] [%d %d]\n", prel, prer, sol1.sa[prel], sol1.sa[prel] + lenl - 1, sol1.sa[prer], sol1.sa[prer] + lenr - 1);
		int a = min(sol1.que(prel, prer), min(lenl, lenr)),
			b = min(sol2.que(sol2.rank[n-sol1.sa[prel]-lenl+2], sol2.rank[n-sol1.sa[prer]-lenr+2]), min(lenl, lenr));
//		printf("%d %d\n", a, b);
		printf("%lld\n", (LL)a * a + (LL)b * b);
	}
	
	return 0;
}