解题思路：
fail树上用权值线段树合并求right/endpos集合，再用倍增找到待查询串对应节点，然后权值线段树求第k大。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,q;
char s[maxn];
namespace SegTree{
int sum[maxn*100],L[maxn*100],R[maxn*100];
int tot1;
int update(int rt,int l,int r,int pos,int val){
int nrt=++tot1;
L[nrt]=L[rt]; R[nrt]=R[rt]; sum[nrt]=sum[rt]+val;
if(l!=r){
int mid=(l+r)>>1;
if(pos<=mid)L[nrt]=update(L[rt],l,mid,pos,val);
else R[nrt]=update(R[rt],mid+1,r,pos,val);
}
return nrt;
}
int merge(int rt1,int rt2){
if(!rt1 || !rt2)return rt1|rt2;
int nrt=++tot1;
L[nrt]=L[rt1]; R[nrt]=R[rt1]; sum[nrt]=sum[rt1]+sum[rt2];
L[nrt]=merge(L[rt1],L[rt2]);
R[nrt]=merge(R[rt1],R[rt2]);
return nrt;
}
int query(int rt,int l,int r,int k){
if(l==r)return l;
int mid=(l+r)>>1;
if(k<=sum[L[rt]])return query(L[rt],l,mid,k);
return query(R[rt],mid+1,r,k-sum[L[rt]]);
}
}using namespace SegTree;
namespace Suffix_Automaton{
int ch[maxn<<1][26],fa[maxn<<1],len[maxn<<1];
int last,tot;
int rt[maxn],T[maxn<<1];
int Fa[maxn<<1][20];
inline void init(){
last=tot=1;
len[1]=fa[0]=0;
memset(ch[1],0,sizeof(ch[1]));
T[1]=0;
}
inline int newnode(){
++tot;
len[tot]=fa[tot]=0;
memset(ch[tot],0,sizeof(ch[tot]));
T[tot]=0;
return tot;
}
inline void extend(int c,int right){
int p=last,cur=newnode();
len[cur]=len[last]+1;
last=cur;
rt[right]=cur;
T[cur]=update(T[cur],1,n,right,1);
while(p && !ch[p][c]){
ch[p][c]=cur;
p=fa[p];
}
if(!p)fa[cur]=1;
else{
int q=ch[p][c];
if(len[p]+1==len[q])fa[cur]=q;
else{
int clone=newnode();
len[clone]=len[p]+1;
memcpy(ch[clone],ch[q],sizeof(ch[q]));
fa[clone]=fa[q];
fa[q]=fa[cur]=clone;
while(ch[p][c]==q){
ch[p][c]=clone;
p=fa[p];
}
}
}
}
int c[maxn<<1],A[maxn<<1];
inline void init(char *a,int l){
init();
for(int i=1;i<=l;i++)extend(a[i]-'a',i);
for(int i=0;i<=tot;i++)c[i]=0;
for(int i=1;i<=tot;i++)++c[len[i]];
for(int i=1;i<=tot;i++)c[i]+=c[i-1];
for(int i=1;i<=tot;i++)A[--c[len[i]]]=i;
for(int i=tot-1;i>=1;i--)T[fa[A[i]]]=merge(T[fa[A[i]]],T[A[i]]);
for(int i=1;i<=tot;i++)Fa[i][0]=fa[i];
for(int k=1;k<=19;k++)for(int i=1;i<=tot;i++)Fa[i][k]=Fa[Fa[i][k-1]][k-1];
}
inline void solve(int l,int r,int k){
int u=rt[r],length=r-l+1;
if(len[fa[u]]+1>length){
for(int k=19;k>=0;k--)if(len[fa[Fa[u][k]]]+1>length)u=Fa[u][k];
u=fa[u];
}
if(k<=sum[T[u]])printf("%d
",query(T[u],1,n,k)-length+1);
else printf("-1
");
}
}using namespace Suffix_Automaton;
int main()
{
//#ifndef ONLINE_JUDGE
// freopen("in.txt","r",stdin);
//#endif
int T;
scanf("%d",&T);
while(T--){
tot1=0;
scanf("%d %d",&n,&q);
scanf("%s",s+1);
init(s,n);
int l,r,k;
while(q--){
scanf("%d %d %d",&l,&r,&k);
solve(l,r,k);
}
}
return 0;
}