#include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=1e5+,mod=;

 char buf[N];

 int s[N],sa[N],buf1[N],buf2[N],c[N],n,rnk[N],ht[N],ST[N][],Log[N],m;

 void Sort(int* x,int* y,int m) {

     for(int i=; i<m; ++i)c[i]=;

     for(int i=; i<n; ++i)++c[x[i]];

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

     for(int i=n-; i>=; --i)sa[--c[x[y[i]]]]=y[i];

 }

 void da(int* s,int n,int m=) {

     int *x=buf1,*y=buf2;

     x[n]=y[n]=-;

     for(int i=; i<n; ++i)x[i]=s[i],y[i]=i;

     Sort(x,y,m);

     for(int k=; k<n; k<<=) {

         int p=;

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

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

         Sort(x,y,m),p=,y[sa[]]=;

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

         if(p==n)break;

         swap(x,y),m=p;

     }

 }

 void getht() {

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

     ht[]=;

     for(int i=,k=; i<n; ++i) {

         if(k)--k;

         if(!rnk[i])continue;

         for(; s[i+k]==s[sa[rnk[i]-]+k]; ++k);

         ht[rnk[i]]=k;

     }

 }

 void initST() {

     for(int i=; i<n; ++i)ST[i][]=ht[i];

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

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

             ST[i][j]=min(ST[i][j-],ST[i+(<<(j-))][j-]);

 }

 int lcp(int l,int r) {

     if(l==r)return n-sa[l];

     if(l>r)swap(l,r);

     l++;

     int k=Log[r-l+];

     return min(ST[l][k],ST[r-(<<k)+][k]);

 }

 int rt[N],ls[N*],rs[N*],sum[N*],tot;

 #define mid ((l+r)>>1)

 int cpy(int v) {int u=++tot; ls[u]=ls[v],rs[u]=rs[v],sum[u]=sum[v]; return u;}

 void upd(int& u,int v,int p,int l=,int r=n-) {

     u=cpy(v);

     sum[u]++;

     if(l==r)return;

     p<=mid?upd(ls[u],ls[v],p,l,mid):upd(rs[u],rs[v],p,mid+,r);

 }

 int qry(int u,int v,int k,int l=,int r=n-) {

     if(l==r)return l;

     int cnt=sum[ls[u]]-sum[ls[v]];

     return k<=cnt?qry(ls[u],ls[v],k,l,mid):qry(rs[u],rs[v],k-cnt,mid+,r);

 }

 void build() {

     da(s,n),getht(),initST();

     tot=;

     for(int i=; i<=n; ++i)upd(rt[i],rt[i-],sa[i-]);

 }

 int main() {

     Log[]=-;

     for(int i=; i<N; ++i)Log[i]=Log[i>>]+;

     int T;

     for(scanf("%d",&T); T--;) {

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

         for(int i=; i<n; ++i)s[i]=buf[i];

         s[n]=;

         build();

         while(m--) {

             int l,r,k;

             scanf("%d%d%d",&l,&r,&k);

             l--,r--;

             int L,R,M=rnk[l],len=r-l+;

             L=R=M;

             for(int i=Log[n]; i>=; --i)if(L-(<<i)>=&&lcp(M,L-(<<i))>=len)L-=(<<i);

             for(int i=Log[n]; i>=; --i)if(R+(<<i)<n&&lcp(M,R+(<<i))>=len)R+=(<<i);

             printf("%d\n",k<=sum[rt[R+]]-sum[rt[L]]?qry(rt[R+],rt[L],k)+:-);

         }

     }

     return ;

 }

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=2e5+,M=;

 char s[N];

 int n,m,fa[N],go[N][M],mxl[N],last,tot,samrt[N],c[N],ss[N],Fa[N][];

 int rt[N],ls[N*],rs[N*],sum[N*],tot2;

 #define mid ((l+r)>>1)

 int cpy(int v) {int u=++tot2; ls[u]=ls[v],rs[u]=rs[v],sum[u]=sum[v]; return u;}

 void upd(int& u,int v,int p,int l=,int r=n) {

     u=cpy(v),sum[u]++;

     if(l==r)return;

     p<=mid?upd(ls[u],ls[v],p,l,mid):upd(rs[u],rs[v],p,mid+,r);

 }

 void mg(int& w,int u,int v) {

     if(!u||!v) {w=u|v; return;}

     w=cpy(u),sum[w]+=sum[v];

     mg(ls[w],ls[u],ls[v]),mg(rs[w],rs[u],rs[v]);

 }

 int qry(int u,int k,int l=,int r=n) {

     if(l==r)return l;

     return k<=sum[ls[u]]?qry(ls[u],k,l,mid):qry(rs[u],k-sum[ls[u]],mid+,r);

 }

 int newnode(int l) {int u=++tot; rt[u]=,mxl[u]=l,memset(go[u],,sizeof go[u]); return u;}

 void add(int ch,int r) {

     int p=last,np=last=newnode(mxl[p]+);

     samrt[r]=np;

     upd(rt[np],rt[np],r,);

     for(; p&&!go[p][ch]; p=fa[p])go[p][ch]=np;

     if(!p)fa[np]=;

     else {

         int q=go[p][ch];

         if(mxl[q]==mxl[p]+)fa[np]=q;

         else {

             int nq=newnode(mxl[p]+);

             memcpy(go[nq],go[q],sizeof go[q]);

             fa[nq]=fa[q],fa[q]=fa[np]=nq;

             for(; p&&go[p][ch]==q; p=fa[p])go[p][ch]=nq;

         }

     }

 }

 void build() {

     tot=tot2=,last=newnode();

     for(int i=; i<n; ++i)add(s[i]-'a',i+);

     for(int i=; i<=tot; ++i)c[i]=;

     for(int i=; i<=tot; ++i)++c[mxl[i]];

     for(int i=; i<=tot; ++i)c[i]+=c[i-];

     for(int i=; i<=tot; ++i)ss[--c[mxl[i]]]=i;

     for(int i=tot-; i>; --i)mg(rt[fa[ss[i]]],rt[fa[ss[i]]],rt[ss[i]]);

     for(int i=; i<=tot; ++i)Fa[i][]=fa[i];

     for(int k=; k<; ++k)for(int i=; i<=tot; ++i)Fa[i][k]=Fa[Fa[i][k-]][k-];

 }

 int main() {

     int T;

     for(scanf("%d",&T); T--;) {

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

         build();

         while(m--) {

             int l,r,k;

             scanf("%d%d%d",&l,&r,&k);

             int u=samrt[r],len=r-l+;

             if(mxl[fa[u]]+>len) {

                 for(int k=; k>=; --k)if(mxl[fa[Fa[u][k]]]+>len)u=Fa[u][k];

                 u=fa[u];

             }

             printf("%d\n",k<=sum[rt[u]]?qry(rt[u],k)-len+:-);

         }

     }

     return ;

 }