#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N= 1e8+5;
ll a[N];
pair<ll,ll>sg[4*N];

void build(int node, int start, int ending)
{
    if(start==ending)
    {
        sg[node]= {a[start],a[start]};
        return;
    }

    int mid = (start+ending-1)/2;

    build(node*2, start, mid);
    build(node*2+1, mid+1, ending);

    sg[node].first = min(sg[node*2].second, sg[node*2+1].second);
    sg[node].second = max(sg[node*2].first, sg[node*2+1].first);
}

void update(int node, int start, int end, int idx, int val)
{
    if(start==end)
    {
        sg[node]={val,val};
        a[idx]=val;
        return;
    }

    int mid = (start+end-1)/2;

    if(idx<=mid)
        update(node*2, start, mid, idx, val);
    else
        update(node*2+1, mid+1, end, idx, val);

    sg[node].first = min(sg[node*2].second, sg[node*2+1].second);
    sg[node].second = max(sg[node*2].first, sg[node*2+1].first);

}

//int query (int node, int start, int ending, int l, int r)
//{
//    if(r<start || l>ending)
//        return 0;
//    if(l<=start && r>=ending)
//        return sg[node];
//
//    int mid = (start+ending)/2;
//
//    int q1 = query(node*2, start, mid, l, r);
//    int q2 = query(node*2+1, mid+1, ending, l, r);
//
//    return q1+q2;
//
//}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,q; cin>>n>>q;

    for(int i=1; i<=n; i++) cin>>a[i];

    build(1,1,n);


    while(q--)
    {
        int index,value, turn;

        cin>>index>>value>>turn;

        update(1,1,n,index,value);

        if(turn==0)
        {
            cout<<sg[1].first<<endl;
        }
        else
            cout<<sg[1].second<<endl;
    }


    return 0;
}