#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

const int N = 2e5 + 9;

struct Segment_Tree {
    pair<int, int> t[4 * N];

    pair<int, int> merge(auto &l, auto &r) { // <== Change this function
        return {min(l.second, r.second), max(l.first, r.first)};
    }
    void build(int node, int st, int en, vector<int> &arr) { //=> O(N)
        if (st == en) {
            t[node] = {arr[st], arr[st]};
            return;
        }
        int mid = (st + en) >> 1;
        build(node << 1, st, mid, arr); // divide left side
        build(node << 1 | 1, mid + 1, en, arr); // divide right side
        // Merging left and right portion
        auto &Cur = t[node];
        auto &Left = t[node << 1];
        auto &Right = t[node << 1 | 1];
        Cur = merge(Left, Right);
        return;
    }
    void update(int node, int st, int en, int idx, int val) { //=> O(log n)
        if (st == en) {
            t[node] = {val, val};
            return;
        }
        int mid = (st + en) >> 1;
        if (idx <= mid) update(node << 1, st, mid, idx, val);
        else update(node << 1 | 1, mid + 1, en, idx, val);
        // Merging left and right portion
        auto &Cur = t[node];
        auto &Left = t[node << 1];
        auto &Right = t[node << 1 | 1];
        Cur = merge(Left, Right);
        return;
    }
} st1;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, qry;
    cin >> n >> qry;
    vector<int> arr(n + 1);
    for(int i = 1; i <= n; i++) cin >> arr[i];
    st1.build(1, 1, n, arr);
    int i, v, q;
    while(qry--) {
        cin >> i >> v >> q;
        assert(q <= 1000000000 && arr[i] <= 1000000000);
        st1.update(1, 1, n, i, v);
        if(q) cout << st1.t[1].second << endl;
        else cout << st1.t[1].first << endl;
    }
    return 0;
}