1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| #include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline ll read()
{
ll x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200010;
const int K=19;
int base[N],t[N],l2[N];
inline bool cmp(int x,int y,int k)
{
return t[x]==t[y]&&t[x+k]==t[y+k];
}
struct SuufixArray{
int height[N],sa[N],rk[N],f[N][K],len;
ll sum[N];
inline void rsort(int n,int m)
{
fo(i,0,m) base[i]=0;
fo(i,1,n) base[rk[t[i]]]++;
fo(i,1,m) base[i]+=base[i-1];
fd(i,n,1) sa[base[rk[t[i]]]--]=t[i];
}
inline void build(char *s,int n)
{
memset(t,0,sizeof(t));
len=n; s[n+1]=0;
fo(i,1,n) t[i]=i,rk[i]=s[i]-'a'+1;
rsort(n,128);
for(int w=1,p=0;p<n;w<<=1)
{
p=0;
fo(i,n-w+1,n) t[++p]=i;
fo(i,1,n) if(sa[i]>w) t[++p]=sa[i]-w;
rsort(n,p);
fo(i,1,n) t[i]=rk[i];
rk[sa[1]]=p=1;
fo(i,2,n) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
for(int i=1,j,k=0;i<=n;height[rk[i++]]=k)
for(j=sa[rk[i]-1],(k?(k--):0);s[i+k]==s[j+k];k++);
fo(i,1,n) f[i][0]=height[i],sum[i]=sum[i-1]+(n-sa[i]+1)-height[i];
fo(j,1,K-1)
fo(i,1,n)
{
f[i][j]=f[i][j-1];
if(i+(1<<j)-1<=n) f[i][j]=min(f[i][j],f[i+(1<<(j-1))][j-1]);
}
}
inline int ask(int x,int y)
{
if(x==y) return len-x+1;
x=rk[x]; y=rk[y];
if(x>y) swap(x,y);
x++;
int k=l2[y-x+1];
return min(f[x][k],f[y-(1<<k)+1][k]);
}
inline void calc(ll k,int &x,int &l)
{
int tmp=lower_bound(sum+1,sum+len+1,k)-sum;
x=sa[tmp];
l=len-sa[tmp]+1-(sum[tmp]-k);
}
}SA[2];
inline ll sqr(int x) {return 1ll*x*x;}
int n,m;
char s[N];
int main()
{
n=read(); m=read();
fo(i,2,n) l2[i]=l2[i>>1]+1;
scanf("%s",s+1);
SA[0].build(s,n);
reverse(s+1,s+n+1);
SA[1].build(s,n);
ll sum=SA[0].sum[n];
ll u,v;
int x,y,l1,l2,len;
fo(i,1,m)
{
u=read(),v=read();
if(u>sum||v>sum) printf("%d\n",-1);
else
{
SA[0].calc(u,x,l1);
SA[0].calc(v,y,l2);
len=min(l1,l2);
printf("%lld\n",sqr(min(len,SA[0].ask(x,y)))+sqr(min(len,SA[1].ask(n-(x+l1-1)+1,n-(y+l2-1)+1))));
}
}
return 0;
}
|