// TranThienPhuc2657
// 17 ngay truoc khi toi ki thi Hoc sinh gioi Quoc gia 2025 - 2026, 25/12/2025.
#include <bits/stdc++.h>
using namespace std;
#define file "KIEMTRAPIN"
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define Sz(x) ((int) (x).size())
#define getBit(mask, i) (((mask) >> (i)) & 1)
template <typename T1, typename T2> bool mini(T1 &A, T2 B) {if (A > B) A = B; else return 0; return 1;}
template <typename T1, typename T2> bool maxi(T1 &A, T2 B) {if (A < B) A = B; else return 0; return 1;}
const int inf = 2e9 + 7;
const ll linf = 1e18l + 7;
const int mod = 1e9 + 7;
const int N = 4e5 + 5;
const int BLOCK_SIZE = 650;
int n, q, a[N];
int idB[N];
struct Block {
int l, r;
priority_queue <int> pq;
vector <int> Q;
Block() {}
Block(int _l, int _r, int idBlock) : l(_l), r(_r), pq(a + _l, a + _r + 1) {
for (int i = l; i <= r; i++) idB[i] = idBlock;
}
int build(int lq, int rq, int x) {
if (!Q.empty()) {
priority_queue <int, vector <int>, greater <int>> can(Q.begin(), Q.end());
Q.clear();
for (int i = l; i <= r; i++) if (a[i] > can.top()) {
can.push(a[i]);
a[i] = can.top();
can.pop();
}
}
for (int i = lq; i <= rq; i++) if (a[i] > x) swap(a[i], x);
pq = priority_queue <int> (a + l, a + r + 1);
return x;
}
int update(int x) {
if (!pq.empty() and x < pq.top()) {
pq.push(x); Q.pb(x);
x = pq.top(); pq.pop();
}
return x;
}
};
vector <Block> B;
// inp
void inp() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
}
// init
void init() {
int numBlock = (n - 1) / BLOCK_SIZE + 1;
B = vector <Block> (numBlock + 5);
int l = 1;
for (int i = 1; i < numBlock; i++) {
B[i] = Block(l, l + BLOCK_SIZE - 1, i);
l += BLOCK_SIZE;
}
B[numBlock] = Block(l, n, numBlock);
}
// proc
void update(int l, int r, int &p) {
int lB = idB[l], rB = idB[r];
if (lB == rB) p = B[lB].build(l, r, p);
else {
p = B[lB].build(l, B[lB].r, p);
for (int id = lB + 1; id < rB; id++) p = B[id].update(p);
p = B[rB].build(B[rB].l, r, p);
}
}
void proc() {
for (int i = 1; i <= q; i++) {
int l, r, p; cin >> l >> r >> p;
if (l > r) {
update(l, n, p);
update(1, r, p);
}
else update(l, r, p);
cout << p << "\n";
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(file".inp", "r")) {
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
inp();
init();
proc();
cerr << "Time elapsed: " << TIME << "s.\n";
return 0;
}
