#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

char s[maxn];

int n, tot;

int root[maxn];

struct node {

    int sum;

    int lc, rc;

};

node tr[maxn * 50];

struct SA {

    int sa[maxn], x[maxn], y[maxn], c[maxn];

    int rank[maxn], height[maxn], h[maxn];

    int f[maxn][18];

    void build_sa(int m) {

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

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

    //c数组是桶

    //x[i]是第i个元素的第一关键字

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

    //做c的前缀和，我们就可以得出每个关键字最多是在第几名

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

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

            int num=0;

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

    //y[i]表示第二关键字排名为i的数，第一关键字的位置

    //第n-k+1到第n位是没有第二关键字的 所以排名在最前面

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

    //排名为i的数 在数组中是否在第k位以后

    //如果满足(sa[i]>k) 那么它可以作为别人的第二关键字，就把它的第一关键字的位置添加进y就行了

    //所以i枚举的是第二关键字的排名，第二关键字靠前的先入队

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

    //初始化c桶

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

    //因为上一次循环已经算出了这次的第一关键字 所以直接加就行了

            for (int i=2; i<=m; ++i) c[i]+=c[i-1]; //第一关键字排名为1~i的数有多少个

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

    //因为y的顺序是按照第二关键字的顺序来排的

    //第二关键字靠后的，在同一个第一关键字桶中排名越靠后

    //基数排序

            swap(x,y);

    //这里不用想太多，因为要生成新的x时要用到旧的，就把旧的复制下来，没别的意思

            x[sa[1]]=1;

            num=1;

            for (int i=2; i<=n; ++i)

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

    //因为sa[i]已经排好序了，所以可以按排名枚举，生成下一次的第一关键字

            if (num==n) break;

            m=num;

    //这里就不用那个122了，因为都有新的编号了

        }

    }

    void get_height() {

        int k=0;

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

        for (int i=1; i<=n; ++i) {

            if (rank[i]==1) continue;//第一名height为0

            if (k) --k;//h[i]>=h[i-1]-1;

            int j=sa[rank[i]-1];

            while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;

            height[rank[i]]=k;//h[i]=height[rk[i]];

        }

        for (int i = 1; i <= n; i++) h[i] = height[rank[i]];

    }

    void build_st() {

        for (int i = 1; i <= n; i++)

            f[i][0] = height[i];

        int t = log(n) / log(2) + 1;

        for (int j = 1; j < t; j++) {

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

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

        }

    }

    int query(int l, int r) {

        if(l > r) return 0;

        int k = log(r - l + 1) / log(2);

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

    }

};

SA solve;

int build(int l, int r) {

    int p = ++tot;

    if (l == r) {

        tr[p].sum = 0;

        tr[p].lc = tr[p].rc = 0;

        return p;

    }

    int mid = (l + r) >> 1;

    tr[p].lc = build(l, mid);

    tr[p].rc = build(mid + 1, r);

    tr[p].sum = tr[tr[p].lc].sum + tr[tr[p].rc].sum;

    return p;

}

int insert(int now, int l, int r, int x, int val) {

    int p = ++tot;

    tr[p] = tr[now];

    if(l == r) {

        tr[p].sum = 1;

        return p;

    }

    int mid = (l + r) >> 1;

    if(x <= mid) tr[p].lc = insert(tr[now].lc, l, mid, x, val);

    else tr[p].rc = insert(tr[now].rc, mid + 1, r, x, val);

    tr[p].sum = tr[tr[p].lc].sum + tr[tr[p].rc].sum;

    return p;

}

int query(int lnow, int rnow, int l, int r, int remain) {

    if(l > r) return 0;

    if(l == r) {

        return l;

    }

    int mid = (l + r) >> 1;

    int tmp = tr[tr[rnow].lc].sum - tr[tr[lnow].lc].sum;

    if(tmp >= remain) return query(tr[lnow].lc, tr[rnow].lc, l, mid, remain);

    else return query(tr[lnow].rc, tr[rnow].rc, mid + 1, r, remain - tmp);

}

int main() {

    int T, m, l, r, k, ql, qr;

//    freopen("cin.txt", "r", stdin);

//    freopen("cout.txt", "w", stdout);

    scanf("%d", &T);

    while(T--) {

        tot = 0;

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

        scanf("%s", s + 1);

        for (int i = 1; i <= n; i++)

            s[i] -= ('a' - 1);

        solve.build_sa(30);

        solve.get_height();

        solve.build_st();

        root[0] = build(1, n);

        for (int i = 1; i <= n; i++) {

            root[i] = insert(root[i - 1], 1, n, solve.sa[i], 1);

        }

        for (int i = 1; i <= m; i++) {

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

            int p = solve.rank[l];

            int L = 1, R = p;

            while(L < R) {

                int mid = (L + R) >> 1;

                if(solve.query(mid + 1, p) < r - l + 1) L = mid + 1;

                else R = mid;

            }

            ql = L;

            L = p, R = n;

            while(L < R) {

                int mid = (L + R + 1) >> 1;

                if(solve.query(p + 1, mid) < r - l + 1) R = mid - 1;

                else L = mid;

            }

            qr = R;

            if(qr - ql + 1 < k) printf("-1\n");

            else printf("%d\n", query(root[ql - 1], root[qr], 1, n, k));

        }

    }

}