#include <bits/stdc++.h>
using namespace std;
#define sz(o) ((int)o.size())
#define all(o) o.begin(), o.end()
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repr(i, a, b) for(int i = (a); i >= (b); i--)
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<int> vi;
void fs(int &nn) {
bool neg = false;
register int ch;
nn = 0;
ch = getchar();
if (ch == '-') {
neg = true;
ch = getchar();
}
for (; (ch > 47 && ch < 58); ch = getchar()) nn = nn * 10 + ch - 48;
if (neg) nn *= -1;
}
const int maxn = 111111;
int n, m, maxi;
int a[maxn], rm[maxn];
map<int, int> M;
struct node {
int count;
node *left, *right;
node(int count, node *left, node *right) :count(count), left(left), right(right) {}
};
node *root[maxn];
node *null = new node(0, NULL, NULL);
node* build(node *cur, int l, int r, int c) {
if (l == r) return new node(cur->count + 1, null, null);
else {
int mid = (l + r) >> 1;
node *newNode = new node(0, null, null);
if (c <= mid) {
newNode->right = cur->right;
newNode->left = build(cur->left, l, mid, c);
newNode->count = newNode->left->count + newNode->right->count;
}
else {
newNode->left = cur->left;
newNode->right = build(cur->right, mid + 1, r, c);
newNode->count = newNode->left->count + newNode->right->count;
}
return newNode;
}
}
int query(node *a, node *b, int l, int r, int k) {
if (l == r) return l;
else {
int mid = (l + r) >> 1;
int count = a->left->count - b->left->count;
if (count >= k) return query(a->left, b->left, l, mid, k);
return query(a->right, b->right, mid + 1, r, k - count);
}
}
void solve() {
fs(n);
fs(m);
rep(i, 1, n){
fs(a[i]);
M[a[i]];
}
maxi = 0;
for(auto it = M.begin(); it != M.end(); it++){
M[it->first] = ++maxi;
rm[maxi] = it->first;
}
null->left = null->right = null;
root[0] = null;
rep(i, 1, n) root[i] = build(root[i - 1], 1, maxi, M[a[i]]);
while(m--){
int l, r, k;
fs(l);
fs(r);
fs(k);
printf("%d\n", rm[query(root[r], root[l - 1], 1, maxi, k)]);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
/*ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);*/
cout << setprecision(10);
clock_t b = clock();
solve();
clock_t e = clock();
cerr << (double(e - b) / CLOCKS_PER_SEC) << " sec";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKI2RlZmluZSBzeihvKSAoKGludClvLnNpemUoKSkKI2RlZmluZSBhbGwobykgby5iZWdpbigpLCBvLmVuZCgpCiNkZWZpbmUgcmVwKGksIGEsIGIpIGZvcihpbnQgaSA9IChhKTsgaSA8PSAoYik7IGkrKykKI2RlZmluZSByZXByKGksIGEsIGIpIGZvcihpbnQgaSA9IChhKTsgaSA+PSAoYik7IGktLSkKIAp0eXBlZGVmIGxvbmcgbG9uZyBpbnQgbGw7CnR5cGVkZWYgdmVjdG9yPGxsPiB2bGw7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CiAKdm9pZCBmcyhpbnQgJm5uKSB7CiAgICBib29sIG5lZyA9IGZhbHNlOwogICAgcmVnaXN0ZXIgaW50IGNoOwogICAgbm4gPSAwOwogICAgY2ggPSBnZXRjaGFyKCk7CiAgICBpZiAoY2ggPT0gJy0nKSB7CiAgICAgICAgbmVnID0gdHJ1ZTsKICAgICAgICBjaCA9IGdldGNoYXIoKTsKICAgIH0KICAgIGZvciAoOyAoY2ggPiA0NyAmJiBjaCA8IDU4KTsgY2ggPSBnZXRjaGFyKCkpIG5uID0gbm4gKiAxMCArIGNoIC0gNDg7CiAgICBpZiAobmVnKSBubiAqPSAtMTsKfQogCmNvbnN0IGludCBtYXhuID0gMTExMTExOwppbnQgbiwgbSwgbWF4aTsKaW50IGFbbWF4bl0sIHJtW21heG5dOwptYXA8aW50LCBpbnQ+IE07CiAKc3RydWN0IG5vZGUgewogICAgaW50IGNvdW50OwogICAgbm9kZSAqbGVmdCwgKnJpZ2h0OwogICAgbm9kZShpbnQgY291bnQsIG5vZGUgKmxlZnQsIG5vZGUgKnJpZ2h0KSA6Y291bnQoY291bnQpLCBsZWZ0KGxlZnQpLCByaWdodChyaWdodCkge30KfTsKIApub2RlICpyb290W21heG5dOwpub2RlICpudWxsID0gbmV3IG5vZGUoMCwgTlVMTCwgTlVMTCk7CiAKbm9kZSogYnVpbGQobm9kZSAqY3VyLCBpbnQgbCwgaW50IHIsIGludCBjKSB7CiAgICBpZiAobCA9PSByKSByZXR1cm4gbmV3IG5vZGUoY3VyLT5jb3VudCArIDEsIG51bGwsIG51bGwpOwogICAgZWxzZSB7CiAgICAgICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgICAgICBub2RlICpuZXdOb2RlID0gbmV3IG5vZGUoMCwgbnVsbCwgbnVsbCk7CiAgICAgICAgaWYgKGMgPD0gbWlkKSB7CiAgICAgICAgICAgIG5ld05vZGUtPnJpZ2h0ID0gY3VyLT5yaWdodDsKICAgICAgICAgICAgbmV3Tm9kZS0+bGVmdCA9IGJ1aWxkKGN1ci0+bGVmdCwgbCwgbWlkLCBjKTsKICAgICAgICAgICAgbmV3Tm9kZS0+Y291bnQgPSBuZXdOb2RlLT5sZWZ0LT5jb3VudCArIG5ld05vZGUtPnJpZ2h0LT5jb3VudDsKICAgICAgICB9CiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIG5ld05vZGUtPmxlZnQgPSBjdXItPmxlZnQ7CiAgICAgICAgICAgIG5ld05vZGUtPnJpZ2h0ID0gYnVpbGQoY3VyLT5yaWdodCwgbWlkICsgMSwgciwgYyk7CiAgICAgICAgICAgIG5ld05vZGUtPmNvdW50ID0gbmV3Tm9kZS0+bGVmdC0+Y291bnQgKyBuZXdOb2RlLT5yaWdodC0+Y291bnQ7CiAgICAgICAgfQogICAgICAgIHJldHVybiBuZXdOb2RlOwogICAgfQp9CiAKaW50IHF1ZXJ5KG5vZGUgKmEsIG5vZGUgKmIsIGludCBsLCBpbnQgciwgaW50IGspIHsKICAgIGlmIChsID09IHIpIHJldHVybiBsOwogICAgZWxzZSB7CiAgICAgICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgICAgICBpbnQgY291bnQgPSBhLT5sZWZ0LT5jb3VudCAtIGItPmxlZnQtPmNvdW50OwogICAgICAgIGlmIChjb3VudCA+PSBrKSByZXR1cm4gcXVlcnkoYS0+bGVmdCwgYi0+bGVmdCwgbCwgbWlkLCBrKTsKICAgICAgICByZXR1cm4gcXVlcnkoYS0+cmlnaHQsIGItPnJpZ2h0LCBtaWQgKyAxLCByLCBrIC0gY291bnQpOwogICAgfQp9CiAKdm9pZCBzb2x2ZSgpIHsKICAgIGZzKG4pOwogICAgZnMobSk7CiAgICByZXAoaSwgMSwgbil7CiAgICAgICAgZnMoYVtpXSk7CiAgICAgICAgTVthW2ldXTsKICAgIH0KICAgIG1heGkgPSAwOwogICAgZm9yKGF1dG8gaXQgPSBNLmJlZ2luKCk7IGl0ICE9IE0uZW5kKCk7IGl0KyspewogICAgICAgIE1baXQtPmZpcnN0XSA9ICsrbWF4aTsKICAgICAgICBybVttYXhpXSA9IGl0LT5maXJzdDsKICAgIH0KIAogICAgbnVsbC0+bGVmdCA9IG51bGwtPnJpZ2h0ID0gbnVsbDsKICAgIHJvb3RbMF0gPSBudWxsOwogICAgcmVwKGksIDEsIG4pIHJvb3RbaV0gPSBidWlsZChyb290W2kgLSAxXSwgMSwgbWF4aSwgTVthW2ldXSk7CiAKICAgIHdoaWxlKG0tLSl7CiAgICAgICAgaW50IGwsIHIsIGs7CiAgICAgICAgZnMobCk7CiAgICAgICAgZnMocik7CiAgICAgICAgZnMoayk7CiAgICAgICAgcHJpbnRmKCIlZFxuIiwgcm1bcXVlcnkocm9vdFtyXSwgcm9vdFtsIC0gMV0sIDEsIG1heGksIGspXSk7CiAgICB9Cn0KIAppbnQgbWFpbigpIHsKICAgICNpZm5kZWYgT05MSU5FX0pVREdFCiAgICBmcmVvcGVuKCJpbi50eHQiLCAiciIsIHN0ZGluKTsKICAgIGZyZW9wZW4oIm91dC50eHQiLCAidyIsIHN0ZG91dCk7CiAgICAjZW5kaWYKICAgIC8qaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKE5VTEwpOwogICAgY291dC50aWUoTlVMTCk7Ki8KICAgIGNvdXQgPDwgc2V0cHJlY2lzaW9uKDEwKTsKICAgIGNsb2NrX3QgYiA9IGNsb2NrKCk7CiAgICBzb2x2ZSgpOwogICAgY2xvY2tfdCBlID0gY2xvY2soKTsKICAgIGNlcnIgPDwgKGRvdWJsZShlIC0gYikgLyBDTE9DS1NfUEVSX1NFQykgPDwgIiBzZWMiOwogICAgcmV0dXJuIDA7Cn0g