#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
 
#define int ll
#define all(it) it.begin(),it.end()
#define ord_set(T) tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update> 

void work(){
    int n,q;
    cin >> n >> q;
    vll v(n);
    for (auto &c : v) cin >> c;
    
    auto res = [&](auto &&res, int l, int r, int p) -> int {
        if (l == r) return v[l];
        int mid = (l+r)/2;
        if (p) return max(res(res,l,mid,!p), res(res,mid+1,r,!p));
        else return min(res(res,l,mid,!p), res(res,mid+1,r,!p));
    };

    for (int i=0;i<q;i++){
        int a,b,p;
        cin >> a >> b >> p;
        int prev = v[a-1];
        v[a-1] = b;
        cout << res(res,0,n-1,p) << '\n';
        v[a-1] = prev;
    }
}


int32_t main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    work();
    
    return 0;
}