#include <bits/stdc++.h>
//#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div ___div
#define next ___next
#define prev ___prev
#define left ___left
#define right ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;
//const int mod = ;
//void add (int &a, const int&b){
// a+=b;
// if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
// a-=b;
// if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
// a*=b;
// a%=mod;
//}
template<class X, class Y>
bool minimize(X &x, const Y&y){
if (x<=y) return false;
else{
x = y;
return true;
}
}
template<class X, class Y>
bool maximize (X &x, const Y&y){
if (x>=y) return false;
else{
x = y;
return true;
}
}
/////////////////////////////////////////////////////////////////////////////////
//// dang nhap ham
//#ifndef davele
//
//#endif // davele
//
//// chay thu ham main:
//
//#ifdef davele
//
//#endif // davele
////////////////////////////////////////////////////////////////////////////
//const int lim = , limit = , inf = ;
const string name = "kiemtrapin";
const int blocksize = 650, lim = 4e5, limit = lim+5;
int n, A[limit];
int q;
struct bl{
int st, en;
priority_queue <int> q;
vi news;
int slow_up (int l, int r, int num){
if (news.size()>=1){
pq < int, vector<int>, greater<int> > candidate(news.begin(), news.end());
for (int i=st; i<=en; i++){
if (A[i]>candidate.top()){
candidate.push(A[i]);
A[i] = candidate.top();
candidate.pop();
}
}
news.clear();
}
for (int i=l; i<=r; i++){
if (A[i]>num){
swap(A[i], num);
}
}
q = priority_queue <int>(A+st, A+en+1);
return num;
}
int quick_up(int x){
int ans = x;
if(!q.empty() && x < q.top()){
ans = q.top(); q.pop();
q.push(x), news.emplace_back(x);
}
return ans;
}
};
int numblock;
int inblock[400005];
bl block[5005];
void numbering (){
numblock = 0;
for (int i=1; i<=n; i++){
if (i%blocksize==1){
block[++numblock].st = i;
}
inblock[i] = numblock;
block[numblock].en = i;
}
}
void prep(){
//
numbering();
// for (int i=1; i<=n; i++) cerr<<inblock[i]<<"\n";
for (int i=1; i<=n; i++){
block[inblock[i]].q.push(A[i]);
}
}
int update (int st, int en, int val){
// cerr<<st<<" "<<en<<" "<<val<<" "<<inblock[st]<<" "<<inblock[en]<<"\n";
int fib = inblock[st], lab = inblock[en];
if (fib==lab) return block[fib].slow_up(st, en, val);
else{
val = block[fib].slow_up(st, block[fib].en, val);
for (int i=fib+1; i<lab; i++) val = block[i].quick_up(val);
val = block[lab].slow_up(block[lab].st, en, val);
return val;
}
}
int query (int st, int en, int val){
if (st<=en) return update (st, en, val);
else{
val = update(st, n, val);
return update(1, en, val);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//
if (fopen((name+".inp").c_str(), "r")){
freopen ((name+".inp").c_str(), "r", stdin);
freopen ((name+".out").c_str(), "w", stdout);
}
//
cin>>n>>q;
for (int i=1; i<=n; i++) cin>>A[i];
//
prep();
for (int i=1; i<=q; i++){
int s ,t, x;
cin>>s>>t>>x;
cout<<query(s, t, x)<<"\n";
}
}
