#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
//快读
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 << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
const int N = 400010;
int n, m;
int a[N];   //维护的序列
int ans[N]; // 结果

struct Node {
    // op=1 插入, op=-1 删除, op=2 查询
    int op;
    // 插入：l:插入的值,用于二分与mid PK,r:位置
    // 删除：l:删除的值,用于二分与mid PK,r:位置
    // 查询 [l,r]：查询范围
    // k:第k小
    int l, r, k;
    int id;
} q[N], lq[N], rq[N];

//树状数组
int tr[N];
void add(int x, int c) {
    for (; x < N; x += x & -x) tr[x] += c;
}
//查询x的个数和
int getSum(int x) {
    int sum = 0;
    for (; x; x -= x & -x) sum += tr[x];
    return sum;
}

void solve(int l, int r, int ql, int qr) {
    if (ql > qr) return; //防止RE，递归边界

    if (l == r) { //递归到叶子结点，找到答案
        for (int i = ql; i <= qr; i++)
            if (q[i].op == 2) ans[q[i].id] = l; //所有查询请求，标识答案
        return;
    }

    int mid = (l + r) >> 1;
    int nl = 0, nr = 0;

    for (int i = ql; i <= qr; i++) {
        if (q[i].op < 2) {
            //插入、删除操作二分
            if (q[i].l <= mid)
                add(q[i].r, q[i].op), lq[++nl] = q[i]; //根据q[i].op的不同，通过一样的add函数，在位置q[i].r处，完成插入+1，删除-1的操作
            else
                rq[++nr] = q[i];
        } else {
            //查询数组二分
            int t = getSum(q[i].r) - getSum(q[i].l - 1);
            if (q[i].k <= t)
                lq[++nl] = q[i];
            else {
                q[i].k -= t;
                rq[++nr] = q[i];
            }
        }
    }

    // 有借有还，再借不难
    for (int i = ql; i <= qr; i++)
        if (q[i].op < 2)
            if (q[i].l <= mid) add(q[i].r, -q[i].op);

    for (int i = 1; i <= nl; i++) q[ql - 1 + i] = lq[i];      //将左儿子操作数组，拷贝到q中，原来的下标是[0~ql-1],现在无缝接上[ql-1+1~ql-1+nl]
    for (int i = 1; i <= nr; i++) q[ql - 1 + nl + i] = rq[i]; //将右儿子操作数组，拷贝到q中，原来的下标是[ql-1+nl+i]

    //继续二分左右儿子
    solve(l, mid, ql, ql + nl - 1), solve(mid + 1, r, ql + nl, qr);
}

int main() {
    int l, r, k, c = 0, qc = 0;
    n = read(), qc = read();
    for (int i = 1; i <= n; i++) a[i] = read(), q[++c] = {1, a[i], i}; // op=1:插入,a[i]:值，i:位置

    for (int i = 1; i <= qc; i++) {
        l = read(), r = read(), k = read();
        q[++c] = {2, l, r, k, i}; // op=2：查询,[l,r]:查询范围,k:第k小,i:查询序号
    }
    //整体二分
    solve(-1e9, 1e9, 1, c); //值域[-1e9,1e9],二分查询区间[1,n+m]

    //结果
    for (int i = 1; i <= qc; i++) printf("%d\n", ans[i]);
    return 0;
}