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

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

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


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

    work();
    
    return 0;
}