//POJ 2104#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#define maxn 100010using namespace std;int tree[30][maxn];int sorted[maxn];int toleft[30][maxn];void build(int l, int r, int dep) {    if (l == r) return;    int mid = (l+r) >> 1;    int same = mid - l + 1;    for (int i=l; i<=r; ++i)        if (tree[dep][i] < sorted[mid])        same--;    int lpos = l;    int rpos = mid+1;    for (int i=l; i<=r; ++i) {        if (tree[dep][i] < sorted[mid])            tree[dep+1][lpos++] = tree[dep][i];        else if (tree[dep][i] == sorted[mid] && same>0) {            tree[dep+1][lpos++] = tree[dep][i];            same--;        }else tree[dep+1][rpos++] = tree[dep][i];        toleft[dep][i] = toleft[dep][l-1]+lpos-l;    }    build(l, mid, dep+1);    build(mid+1, r, dep+1);}int query(int L, int R, int l, int r, int dep, int k) {    if (l == r) return tree[dep][l];    int mid = (L+R)>>1;    int cnt = toleft[dep][r] - toleft[dep][l-1];    if (cnt >= k) {        int newl = L+toleft[dep][l-1]-toleft[dep][L-1];        int newr = newl+cnt-1;        return query(L, mid, newl, newr, dep+1, k);    }else {        int newr = r+toleft[dep][R]-toleft[dep][r];        int newl = newr-(r-l-cnt);        return query(mid+1, R, newl, newr, dep+1, k-cnt);    }}int main() {   // freopen("in.cpp", "r", stdin);    int n, m;    while(~scanf("%d%d", &n, &m)) {        for (int i=1; i<=n; ++i) {            scanf("%d", &tree[0][i]);            sorted[i] = tree[0][i];        }        sort(sorted+1, sorted+1+n);        build(1, n, 0);        while(m--) {            int a, b, c;            scanf("%d%d%d", &a, &b, &c);            printf("%d\n", query(1, n, a, b, 0, c));        }    }    return 0;}

//HDU 4417#include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>using namespace std;const int maxn = 1e5+10;int tree[30][maxn];int toleft[30][maxn];int sorted[maxn];void build(int l, int r, int dep) {    if (l == r) return;    int mid = (l+r) >> 1;    int same = mid - l + 1;    for (int i=l; i<=r; ++i)        if (tree[dep][i] < sorted[mid])        same--;    int lpos = l;    int rpos = mid+1;    for (int i=l; i<=r; ++i) {        if (tree[dep][i] < sorted[mid])            tree[dep+1][lpos++] = tree[dep][i];        else if (tree[dep][i] == sorted[mid] && same>0) {            tree[dep+1][lpos++] = tree[dep][i];            same--;        }else tree[dep+1][rpos++] = tree[dep][i];        toleft[dep][i] = toleft[dep][l-1]+lpos-l;    }    build(l, mid, dep+1);    build(mid+1, r, dep+1);}int query(int L, int R, int l, int r, int dep, int k) {    if (l == r) return tree[dep][l];    int mid = (L+R)>>1;    int cnt = toleft[dep][r] - toleft[dep][l-1];    if (cnt >= k) {        int newl = L+toleft[dep][l-1]-toleft[dep][L-1];        int newr = newl+cnt-1;        return query(L, mid, newl, newr, dep+1, k);    }else {        int newr = r+toleft[dep][R]-toleft[dep][r];        int newl = newr-(r-l-cnt);        return query(mid+1, R, newl, newr, dep+1, k-cnt);    }}int solve(int n, int a, int b, int c) {    int ans = 0;    int l = 1;    int r = b - a + 1;    int mid;    while(l<=r) {        mid = (l+r)>>1;        int temp = query(1, n, a, b, 0, mid);        if (temp <= c) {            l = mid+1;            ans = mid;        }else r = mid - 1;    }    return ans;}int main() {   // freopen("in.cpp", "r", stdin);    int t;    int k = 0;    scanf("%d", &t);    while(t--) {        int n, m;        scanf("%d%d", &n, &m);        memset(toleft, 0, sizeof(toleft));        memset(tree, 0, sizeof(tree));        for (int i=1; i<=n; ++i) {            scanf("%d", &tree[0][i]);            sorted[i] = tree[0][i];        }        sort(sorted+1, sorted+1+n);        build(1, n, 0);        printf("Case %d:\n", ++k);        for (int i=0; i<m; ++i) {            int a, b, c;            scanf("%d%d%d",&a, &b, &c);            a++;            b++;            int ans = solve(n, a, b, c);            printf("%d\n", ans);        }    }    return 0;}