LINK

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 1e5 + 50;
const int M = 1e5 + 50;
const int Mod = 1e9 + 7;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int t, n, m;

int a[N], b[N], root[N];

struct Segment
{
    int L, R, sum;
} tree[N * 40];

int cnt = 0;

int update(int l, int r, int pre, int x)
{
    int rt = ++cnt;
    tree[rt].L = tree[pre].L;
    tree[rt].R = tree[pre].R;
    tree[rt].sum = tree[pre].sum + 1;
    if (l == r)
        return rt;
    int mid = l + r >> 1;
    if (x <= mid)
        tree[rt].L = update(l, mid, tree[pre].L, x);
    else
        tree[rt].R = update(mid + 1, r, tree[pre].R, x);
    return rt;
}

int siz;

int query(int nx, int ny, int l, int r, int k)
{
    if (l == r)
        return l;
    int mid = l + r >> 1;
    int x = tree[tree[ny].L].sum - tree[tree[nx].L].sum;
    if (x >= k)
        return query(tree[nx].L, tree[ny].L, l, mid, k);
    else
        return query(tree[nx].R, tree[ny].R, mid + 1, r, k - x);
}

int solve(int x, int y, int k)
{
    int l = x, r = y, res = -1;
    while (l <= r)
    {
        int mid = l + r >> 1;
        int tmp = b[query(root[x - 1], root[y], 1, siz, mid - x)];
        if (tmp <= k)
        {
            l = mid + 1;
            res = max(res, mid - x);
        }
        else
        {
            r = mid - 1;
        }
    }
    if (b[query(root[x - 1], root[y], 1, siz, y - x + 1)] <= k)
    {
        return y - x + 1;
    }
    return res;
}

int main()
{
    int Tcnt = 0;
    t = read();
    while (t--)
    {
        cnt = 0;
        n = read(), m = read();
        for (int i = 1; i <= n; ++i)
            a[i] = read(), b[i] = a[i];
        sort(b + 1, b + n + 1);
        siz = unique(b + 1, b + n + 1) - b - 1;
        for (int i = 1; i <= n; ++i)
        {
            int it = lower_bound(b + 1, b + siz + 1, a[i]) - b;
            root[i] = update(1, siz, root[i - 1], it);
        }
        printf("Case %d:\n", ++Tcnt);
        while (m--)
        {
            int l = read(), r = read(), k = read();
            printf("%d\n", solve(l + 1, r + 1, k));
        }
    }
    return 0;
}