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

const int N = 2e5+2;

int th_tree[4*N], roy_tree[4*N], a[N];

void build_th(int n,int b,int e,bool mn = 1) {
    if(b == e) {
        th_tree[n] = a[b];
        return;
    }
    int mid = (b + e) / 2;
    build_th(2*n,b,mid,!mn);
    build_th(2*n+1,mid+1,e,!mn);
    if(mn) th_tree[n] = min(th_tree[2*n],th_tree[2*n+1]);
    else th_tree[n] = max(th_tree[2*n],th_tree[2*n+1]);
}

void build_roy(int n,int b,int e,bool mx = 1) {
    if(b == e) {
        roy_tree[n] = a[b];
        return;
    }
    int mid = (b + e) / 2;
    build_roy(2*n,b,mid,!mx);
    build_roy(2*n+1,mid+1,e,!mx);
    if(!mx) roy_tree[n] = min(roy_tree[2*n],roy_tree[2*n+1]);
    else roy_tree[n] = max(roy_tree[2*n],roy_tree[2*n+1]);
}

void upd_th(int n,int b,int e,int idx,int v,bool mn = 1) {
    if(b == e) {
        th_tree[n] = v;
        return;
    }
    int mid = (b + e) / 2;
    if(idx <= mid) upd_th(2*n,b,mid,idx,v,!mn);
    else upd_th(2*n+1,mid+1,e,idx,v,!mn);
    if(mn) th_tree[n] = min(th_tree[2*n],th_tree[2*n+1]);
    else th_tree[n] = max(th_tree[2*n],th_tree[2*n+1]);
}

void upd_roy(int n,int b,int e,int idx,int v,bool mx = 1) {
    if(b == e) {
        roy_tree[n] = v;
        return;
    }
    int mid = (b + e) / 2;
    if(idx <= mid) upd_roy(2*n,b,mid,idx,v,!mx);
    else upd_roy(2*n+1,mid+1,e,idx,v,!mx);
    if(!mx) roy_tree[n] = min(roy_tree[2*n],roy_tree[2*n+1]);
    else roy_tree[n] = max(roy_tree[2*n],roy_tree[2*n+1]);
}

void solve() {
    int n,q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    build_th(1,1,n);
    build_roy(1,1,n);
    while(q--) {
        int i,v,p;
        cin >> i >> v >> p;
        upd_th(1,1,n,i,v);
        upd_roy(1,1,n,i,v);
        if(!p) cout << th_tree[1] << '\n';
        else cout << roy_tree[1] << '\n';
    }
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}