#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[30][100086],t[30];
string s;
signed main() {
    freopen("Time.in","r",stdin);
    freopen("Time.out","w",stdout);
	cin>>n>>q>>s;
	s=" "+s;
	for(int i=1;i<=n;i++){
        int duck=s[i]-'a';	
        t[duck]++;
        a[duck][t[duck]]=i;
	}
	for(int i=1;i<=q;i++){
		int l,r,maxx=-1;
		cin>>l>>r;
		for(int j=0;j<=26;j++){
			int s1=upper_bound(a[j]+1,a[j]+t[j]+1,r)-a[j]-1;
			if(s1==t[j]+1||a[j][s1-1]<l)continue;
			int d=l;
			while(s[d]-'a'==j)d++;
			int du=upper_bound(a[j]+1,a[j]+t[j]+1,d)-a[j];
			int mid=(a[j][s1]+d)/2;
			int s2=upper_bound(a[j]+du+1,a[j]+s1+1,mid)-a[j];
//			mid=(a[j][s1]+d+1)/2;
//			s2=upper_bound(a[j]+du+1,a[j]+s1+1,mid)-a[j];
			maxx=max(maxx,max((a[j][s1]-a[j][s2-1])*(a[j][s2-1]-d),(a[j][s1]-a[j][s2])*(a[j][s2]-d)));
//			cout<<j<<" "<<s1<<" "<<s2<<" "<<" "<<maxx<<endl;;
//			cout<<a[j][s1]<<" "<<a[j][s2]<<" "<<d<<" "<<endl;
		}
		if(maxx==0){
		    maxx--;
        }
		cout<<maxx<<endl;
	}
	return 0;
}