#include <bits/stdc++.h>
using namespace std;

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <iterator>


#define ll long long int
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>

#define loop(i,s,e) for(long long int i=s;i<e;i++)
#define cf(i,e,s) for(long long int i=e;i<=s;i++)
#define rf(i,e,s) for(long long int i=e-1;i>=s;i--)
#define pb push_back
#define eb emplace_back


template <class T>
void print_v(vector<T> &v) { cout << "{"; for (auto x : v) cout << x << ","; cout << "\b}"; }


#define PI 3.1415926535897932384626433832795
#define read(type) readInt<type>()
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
void yes() { cout<<"YES\n"; }
void no() { cout<<"NO\n"; }

typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;






#define f first
#define s second
#define endl '\n'
#define sp <<" "<<
#define pb push_back
#define fora(a) for(auto it:a)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define test int tc; cin>>tc; while(tc--)
#define forn(i,n) for(auto i=0; i<n; i++)
#define printv(a) {for(auto u:a) cout<<u<<" "; cout<<endl;}
#define printm(a) {for(auto u:a) cout<<u.f sp u.s<<endl;}
#define op() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fori(a,b,c) {for(a = c.begin(); a!=b; a++) cout<< *a<< " "; cout<<endl;}
#define fraction(a) cout.unsetf(ios::floatfield); cout.precision(a); cout.setf(ios::fixed,ios::floatfield);

typedef unsigned long long ull;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<int>::iterator vit;
const double eps = 1e-9;

const int NMAX = 100005;

const int MAXX=200000;


const int M0=998244353;

struct N{int l;int r;int d0;int d1;int lc;int rc;};
vector<N> T;
vi A;
int I=0;
int b(int l,int r){
 int i=I++;
 T.push_back({l,r,0,0,-1,-1});
 if(l==r){
  T[i].d0=A[l-1];
  T[i].d1=A[l-1];
 } else{
  int n=r-l+1;
  int m=n/2;
  int mid=l+m-1;
  T[i].lc=b(l,mid);
  T[i].rc=b(mid+1,r);
  T[i].d0= T[T[i].lc].d1 < T[T[i].rc].d1 ? T[T[i].lc].d1 : T[T[i].rc].d1;
  T[i].d1= T[T[i].lc].d0 > T[T[i].rc].d0 ? T[T[i].lc].d0 : T[T[i].rc].d0;
 }
 return i;
}
void u(int i,int p,int v){
 N &x=T[i];
 if(x.l==x.r){
  x.d0=v;
  x.d1=v;
  return;
 }
 int mid=T[x.lc].r;
 p<=mid ? u(x.lc,p,v) : u(x.rc,p,v);
 x.d0= T[x.lc].d1 < T[x.rc].d1 ? T[x.lc].d1 : T[x.rc].d1;
 x.d1= T[x.lc].d0 > T[x.rc].d0 ? T[x.lc].d0 : T[x.rc].d0;
}

int main(){
    ios::sync_with_stdio(false);                                               \
    cin.tie(NULL);                                                             \
    cout.tie(NULL);                                                            \
    
	int n,q;
 cin>>n>>q;
 A.resize(n);
 loop(i,0,n) cin>>A[i];
 T.reserve(4*n);
 I=0;
 int r=b(1,n);
 while(q--){
  int i,v,p;
  cin>>i>>v>>p;
  u(r,i,v);
  cout<<(p==0 ? T[r].d0 : T[r].d1)<<"\n";
 }
   
    
    return 0;
}