/*
 *   Copyright (c) 2025 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
//#define cout file
int a[200005];
pair<int,int> sg[800005];
void build(int node,int start,int end)
{
    if(start==end)
    {
        sg[node] = {a[start],a[start]};
        return;
    }
    int mid = (start + end-1)/2;
    build(node*2,start,mid);
    build(node*2+1,mid+1,end);
    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 ind,int val)
{
    if(start==end)
    {
        sg[node] = {val,val};
        a[ind] = val;
        return;
    }
    int mid = (start+end-1)/2;
    if(ind <= mid) update(node*2,start,mid,ind,val);
    else update(node*2+1,mid+1,end,ind,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);
}

void solve(int tc)
{
    // string outp = "output"+to_string(tc)+".txt";
    // string inp = "input"+to_string(tc)+".txt";
    // ofstream file(outp);
    // freopen(inp.c_str(),"r",stdin);

    int n,q; cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    build(1,1,n);
    while(q--)
    {
        int ind,val,player;
        cin >> ind >> val >> player;
        update(1,1,n,ind,val);
        (player)? cout<<sg[1].second<<'\n': cout<<sg[1].first<<'\n';
    }
}

int ans(int l,int r,int player)
{
    if(l==r) return a[l];
    int mid = (l+r-1)/2;
    int ans1 = ans(l,mid,player^1);
    int ans2 = ans(mid+1,r,player^1);
    return (player)? max(ans1,ans2): min(ans1,ans2);
}

void solve2(int tc)
{
    int n,q; cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    while(q--)
    {
        int ind,val,player;
        cin >> ind >> val >> player;
        a[ind] = val;
        int x = ans(1,n,player);
        cout<<ans(1,n,player)<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    solve2(0);
    // int l=0;
    // int r=99;
    // for(int i=l;i<=99;i++) solve(i);
    // //solve2();
}