#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define szz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int inf = 1e9;
const int B = 640;
struct LazySegTree { // 1-indexed
public:
void make(int _n) {
n = _n;
lg = Log2(n);
sz = (1 << lg);
tree.resize(sz << 1);
fill(tree.begin(), tree.end(), inf);
lazy.resize(sz);
fill(lazy.begin(), lazy.end(), 0);
}
void Set(int i, int val) { tree[--i | sz] = val; }
void Init() { for (int i = sz - 1; i; i--) Pull(i); }
void Update(int l, int r, int f) {
--l |= sz, --r |= sz;
for (int i = lg; i; i--) {
if (l >> i << i != l) Push(l >> i);
if (r + 1 >> i << i != r + 1) Push(r >> i);
}
for (int L = l, R = r; L <= R; L >>= 1, R >>= 1) {
if (L & 1) Apply(L++, f);
if (~R & 1) Apply(R--, f);
}
for (int i = 1; i <= lg; i++) {
if (l >> i << i != l) Pull(l >> i);
if (r + 1 >> i << i != r + 1) Pull(r >> i);
}
}
int Getmin() { return tree[1]; }
private:
int n, lg, sz;
vector<int> tree; vector<int> lazy;
static int Log2(int n) {
int ret = 0;
while (n > 1 << ret) ret++;
return ret;
}
void Apply(int i, int f) {
tree[i] += f;
if (i < sz) lazy[i] += f;
}
void Push(int i) {
Apply(i << 1, lazy[i]);
Apply(i << 1 | 1, lazy[i]);
lazy[i] = 0;
}
void Pull(int i) {
tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
};
struct Bucket{
LazySegTree seg;
priority_queue<int> pq;
vector<int> queries;
vector<int> a;
vector<int> use;
vector<int> nxt;
void init() {
pq = priority_queue<int>(a.begin(), a.end());
use.clear();
int cur = 0;
for (int i=0; i<szz(a); i++) {
if (cur <= a[i]) {
cur = a[i];
use.push_back(i);
}
}
seg.make(szz(use));
nxt.clear();
nxt.resize(szz(use));
cur = 0;
for (int i=0; i<szz(use); i++) {
int r = szz(a);
if (i + 1 < szz(use)) r = use[i+1];
if (use[i] + 1 >= r) {
nxt[i] = cur;
continue;
}
int idx = max_element(a.begin()+use[i]+1, a.begin()+r) - a.begin();
if (cur >= a[idx]) {
nxt[i] = cur;
continue;
}
cur = a[idx];
nxt[i] = cur;
int lo = 0, hi = szz(use) - 1;
while (lo < hi) {
int mid = lo + hi >> 1;
if (a[mid] <= cur) lo = mid + 1;
else hi = mid;
}
seg.Set(i+1, i+1 - lo);
}
seg.Init();
}
void apply() {
vector<int> t;
for (auto &x : queries) {
int idx = lower_bound(nxt.begin(), nxt.end(), x) - nxt.begin();
seg.Update(idx+1, szz(use), -1);
if (seg.Getmin() <= 0) {
for (auto &p : use) t.push_back(a[p]);
sort(t.begin(), t.end());
for (int i=0; i<szz(use); i++) a[use[i]] = t[i];
t.clear();
int cur = x;
for (int i=0; i<szz(a); i++) if (cur <= a[i]) swap(cur, a[i]);
init();
} else t.push_back(x);
}
for (auto &p : use) t.push_back(a[p]);
sort(t.begin(), t.end());
for (int i=0; i<szz(use); i++) a[use[i]] = t[i];
queries.clear();
init();
}
int Push(int x) {
queries.push_back(x);
pq.push(x);
int t = pq.top();
pq.pop();
return t;
}
} buc[B];
int n, q;
int a[400010];
int query(int l, int r, int x) {
int lb = l / B;
int rb = r / B;
buc[lb].apply();
for (int i=l; i<=min({r, n-1, lb*B+B-1}); i++) {
if (x < buc[lb].a[i-lb*B]) {
swap(x, buc[lb].a[i-lb*B]);
}
}
buc[lb].init();
if (lb == rb) return x;
for (int i=lb+1; i<=rb-1; i++) {
x = buc[i].Push(x);
}
buc[rb].apply();
for (int i=rb*B; i<=min(n-1, r); i++) {
if (x < buc[rb].a[i-rb*B]) {
swap(x, buc[rb].a[i-rb*B]);
}
}
buc[rb].init();
return x;
}
int main() {
scanf("%d %d", &n, &q);
for (int i=0; i<n; i++) {
scanf("%d", &a[i]);
buc[i/B].a.push_back(a[i]);
}
for (int i=0; i<=(n-1)/B; i++) {
buc[i].init();
}
while (q --) {
int l, r, x;
scanf("%d %d %d", &l, &r, &x);
l --; r --;
if (l <= r) printf("%d\n", query(l, r, x));
else printf("%d\n", query(0, r, query(l, n-1, x)));
}
return 0;
}
