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

#define int        long long int
#define pb         push_back
#define all(x)     x.begin(),x.end()
#define allr(x)    x.rbegin(),x.rend()
#define ii         pair<int,int>
#define endl       '\n'

const int N = 2e5 + 5;
int a[N];
ii seg[4 * N];

void build(int ind, int b, int e) {
    if(b == e) {
        seg[ind] = {a[b], a[b]};
        return;
    }
    int l = ind << 1, r = l | 1;
    int mid = (e + b - 1) >> 1;
    build(l, b, mid);
    build(r, mid + 1, e);
    seg[ind].first = min(seg[l].second, seg[r].second);
    seg[ind].second = max(seg[l].first, seg[r].first);
}
void update(int ind, int b, int e, int i, int x) {
    if(b > i or e < i)  return;
    if(b == e and b == i) {
        seg[ind] = {x, x};
        return;
    }
    int l = ind << 1, r = l | 1;
    int mid = (e + b - 1) >> 1;
    update(l, b, mid, i, x);
    update(r, mid + 1, e, i, x);
    seg[ind].first = min(seg[l].second, seg[r].second);
    seg[ind].second = max(seg[l].first, seg[r].first);
}
// index based on 1
// TC -> build: O(N)
//    -> query: O(logN)

void pipra(int tc) {
    int n, q;
    cin >> n >> q;
    for(int i = 0 ; i < n ; i++)
        cin >> a[i];
    build(1, 0, n - 1);
    while(q--) {
        int i, v, x;
        cin >> i >> v >> x;
        i--;
        update(1, 0, n - 1, i, v);
        cout << (x ? seg[1].second : seg[1].first) << endl;
    }
}

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

    int t = 1;
    // cin >> t;
    for(int i = 1 ; i <= t ; i++)
        pipra(i);
    return 0;
}