!Wavelet Tree

#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <unordered_set>
#include <complex>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <cassert>
#include <random>

#define sz(a) (int)((a).size())

using namespace std;

mt19937 rnd(239);

typedef long long ll;
typedef long double ld;

const int T = (1 << 20);

vector<int> a[T], b[T], arr, le(T), ri(T), good(T, 0);
int cnt;
const int INF = 1e9 + 1;

void build(int v, int l, int r)
{
    if (l + 1 == r || a[v].size() < 2)
    {
        good[v] = 1;
        return;
    }
    int mid = 1LL * (r + l) / 2LL;
    b[v].assign(a[v].size() + 1, 0);
    le[v] = cnt++;
    ri[v] = cnt++;
    for (int i = 0; i < a[v].size(); i++)
    {
        b[v][i + 1] = b[v][i];
        if (a[v][i] < mid)
        {
            b[v][i + 1]++;
            a[le[v]].push_back(a[v][i]);
        }
        else
            a[ri[v]].push_back(a[v][i]);
    }
    build(le[v], l, mid);
    build(ri[v], mid, r);
}

int kth(int v, int l, int r, int k)
{
    //cout << v << ' ' << l << ' ' << r << ' ' << a[v].size() << endl;
    //cout << good.size() << endl;
   // if (v == 6)
     //   exit(0);
    if (good[v])
        return a[v][0];
    if (b[v][r] - b[v][l] >= k)
        return kth(le[v], b[v][l], b[v][r], k);
    return kth(ri[v], l - b[v][l], r - b[v][r], k - (b[v][r] - b[v][l]));
}

int solve()
{
    ios::sync_with_stdio(0);
    int n;
    if (!(cin >> n))
    {
        return 1;
    }
    int q;
    cin >> q;
    a[1].assign(n, 0);
    for (int &i : a[1])
        cin >> i;
    cnt = 2;
    build(1, -INF, INF);
    while (q--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        l--;
        cout << kth(1, l, r, k) << '\n';
    }
    return 0;
}

int32_t main()
{
    #ifdef ONPC
        freopen("in.txt", "r", stdin);
    #endif
    int T = 100;
    //cin >> T;
    for (int i = 1; i <= T; i++)
    {
        #ifdef ONPC
            cerr << "Test #" << i << ":\n";
        #endif
        if (solve())
            break;
        #ifdef ONPC
            cerr << "_______________________________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1000LL / CLOCKS_PER_SEC << " ms" << endl;
    #endif
    return 0;
}