#include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int N=;

 int n,xx[N],yy[N],cnt[N],bin[];

 LL num[N];

 struct Fleet

 {

     int sa[N],height[N],rank[N],f[N][];

     char s[N];

     int i,j,k,p,m;

     inline void get_sa()

     {

         int *x=xx,*y=yy;m=;

         for(i=;i<m;++i)cnt[i]=;

         for(i=;i<n;++i)++cnt[x[i]=s[i]];

         for(i=;i<m;++i)cnt[i]+=cnt[i-];

         for(i=n-;~i;--i)sa[--cnt[x[i]]]=i;

         for(k=,p=;p<n&&k<=n;k<<=,m=p)

         {

             for(p=,i=n-k;i<n;++i)y[p++]=i;

             for(i=;i<n;++i)if(sa[i]>=k)y[p++]=sa[i]-k;

             for(i=;i<m;++i)cnt[i]=;

             for(i=;i<n;++i)++cnt[x[y[i]]];

             for(i=;i<m;++i)cnt[i]+=cnt[i-];

             for(i=n-;~i;--i)sa[--cnt[x[y[i]]]]=y[i];

             for(swap(x,y),p=,x[sa[]]=,i=;i<n;++i)

                 x[sa[i]]=(y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k])?p-:p++;

         }

     }

     inline void get_rank()

     {

         for(i=;i<n;++i)rank[sa[i]]=i;

         for(k=i=;i<n;height[rank[i++]]=k)

             for(k=k?k-:k,j=sa[rank[i]-];s[i+k]==s[j+k];++k);

     }

     inline void ST()

     {

         for(i=;i<n;++i)f[i][]=height[i];

         for(i=;bin[i]<=n;++i)

             for(j=;j+bin[i]-<n;++j)

                 f[j][i]=min(f[j][i-],f[j+bin[i-]][i-]);

     }

     inline LL query(int l,int r)

     {

         int len=r-l+,k=;

         while(bin[k+]<=len)++k;

         return min(f[l][k],f[r-bin[k]+][k]);

     }

     inline void get_kth(int &st,int &ed,LL rk)

     {

         int ans=lower_bound(num,num+n,rk)-num;

         st=sa[ans],ed=st+height[ans]-+rk-num[ans-];

     }

     inline void intn()

         {get_sa(),get_rank(),ST();}

     inline void calc()

         {for(i=;i<n;++i)num[i]=num[i-]+LL(n-sa[i]-height[i]-);}

 }Sfx,Pre;

 inline LL get_length(LL id1,LL id2)

 {

     register int i,j,k,st[],ed[];

     Sfx.get_kth(st[],ed[],id1);

     Sfx.get_kth(st[],ed[],id2);

     LL val=min(ed[]+1ll-st[],ed[]+1ll-st[]),tmp=val;

     if(st[]!=st[])

         if(Sfx.rank[st[]]<Sfx.rank[st[]])

             tmp=min(tmp,Sfx.query(Sfx.rank[st[]]+,Sfx.rank[st[]]));

         else

             tmp=min(tmp,Sfx.query(Sfx.rank[st[]]+,Sfx.rank[st[]]));

     ed[]=n--ed[],ed[]=n--ed[];

     if(ed[]!=ed[])

         if(Pre.rank[ed[]]<Pre.rank[ed[]])

             val=min(val,Pre.query(Pre.rank[ed[]]+,Pre.rank[ed[]]));

         else

             val=min(val,Pre.query(Pre.rank[ed[]]+,Pre.rank[ed[]]));

     return tmp*tmp+val*val;

 }

 int main()

 {

     register int i,j,m,a,b,q;LL u,v;

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

     for(bin[]=i=;i<=;++i)bin[i]=bin[i-]<<;

     for(i=;i<=n;++i)Pre.s[i-]=Sfx.s[n-i];

     Sfx.s[n]=Pre.s[n]=,n++;

     Sfx.intn();Pre.intn();Sfx.calc();

     while(m--)

     {

         scanf("%lld%lld",&u,&v);

         if(u>num[n-]||v>num[n-])printf("-1\n");

         else printf("%lld\n",get_length(u,v));

     }

 }