#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
#define sq 400
vector<vector<ll>>v;
ll n,q,a,b,c;
multiset<ll>s[1007],s2[1007];
void upd(ll x){
for(ll i=0;i<v[x].size();i++){
s2[x].insert(v[x][i]);
v[x][i]=*s2[x].begin();
s2[x].erase(s2[x].begin());
}
s2[x].clear();
}
ll pocz[1007],kon[1007];
int main(){
cin>>n>>q;
for(ll i=0;i<n;i++){
if(i%sq==0){
pocz[i/sq]=i;
cin>>a;
v.pb({a});
}
else{
cin>>a;
v.back().pb(a);
}
kon[i/sq]=i;
s[i/sq].insert(a);
}
// cout<<v.size()<<" ";
// for(auto j : v){
// for(ll k : j)cout<<k<<" ";
// cout<<"\n";
// }
// cout<<"\n\n";
for(ll i=0;i<q;i++){
cout<<flush;
cin>>a>>b>>c;
a--;
b--;
ll pc=a/sq;
ll kn=b/sq;
upd(pc);
upd(kn);
// for(auto j : v){
// for(ll k : j)cout<<k<<" ";
// cout<<"\n";
// }
//cout<<"\n\n";
b-=kn*sq;
a-=pc*sq;
if(pc==kn && a<=b){
s[pc].insert(c);
for(ll j=a;j<=b;j++){
if(v[pc][j]>c)swap(v[pc][j],c);
}
s[pc].erase(s[pc].find(c));
cout<<c<<"\n";
continue;
}
for(ll j=a;j<v[pc].size();j++){
s[pc].insert(c);
if(v[pc][j]>c)swap(v[pc][j],c);
s[pc].erase(s[pc].find(c));
}
for(ll k=(pc+1)%v.size();k!=kn;k=(k+1)%v.size()){
//cout<<k<<" ";
s2[k].insert(c);
s[k].insert(c);
c=*--s[k].end();
s[k].erase(--s[k].end());
}
for(ll j=0;j<=b;j++){
s[kn].insert(c);
if(v[kn][j]>c)swap(v[kn][j],c);
s[kn].erase(s[kn].find(c));
}
cout<<c<<"\n";
}
}
