// Author : Kamonasish Roy (Bullet)
// Time : 2025-03-20 01:40:06

#include<bits/stdc++.h>
using namespace std;
const long long M=1e6,MOD=1e9+7;
typedef long long ll;
int Roy[M];
int Thakur[M];
int Parent[M];
int a[M];
vector<int>binarylift[M];
int L[M];
int R[M];
void make_tree(int node,int l,int r,int cnt){
	R[node]=cnt;
	if(l==r){
		Roy[node]=Thakur[node]=a[l];
		L[l]=node;
		return;
	}
	int mid=l+(r-l)/2;
	if(abs(r-l+1)%2==1)mid--;
	int left=2*node;
	int right=2*node+1;
	Parent[left]=node;
	Parent[right]=node;
	int d=cnt+1;
	binarylift[node].push_back(left);
	binarylift[node].push_back(right);
	make_tree(left,l,mid,d);
	make_tree(right,mid+1,r,d);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
   // cin>>t;
    while(t--){
      int n,q;
      cin>>n>>q;
      for(int i=1;i<=n;i++)cin>>a[i];
      for(int i=1;i<M;i++)Parent[i]=i;
      make_tree(1,1,n,1);
      for(int i=M-1;i>=1;i--){
      	if(Parent[i]==i)continue;
      	int x=binarylift[Parent[i]][0];
      	int y=binarylift[Parent[i]][1];
      	int move=R[x];
      	if(move % 2==0){
      		Roy[Parent[i]]=max(Roy[x],Roy[y]);
      		Thakur[Parent[i]]=min(Thakur[x],Thakur[y]);
      	}
      	else{
      		Roy[Parent[i]]=min(Roy[x],Roy[y]);
      		Thakur[Parent[i]]=max(Thakur[x],Thakur[y]);
      	}
      }
     while(q--){
     	int id,v,op;
     	cin>>id>>v>>op;
     	int cur=L[id];
     	Roy[cur]=v;
     	Thakur[cur]=v;
     	while(Parent[cur]!=cur){
     		cur=Parent[cur];
     		int x=binarylift[cur][0];
     		int y=binarylift[cur][1];
     		int move=R[x];
     		if(move % 2==0){
     			Roy[cur]=max(Roy[x],Roy[y]);
     			Thakur[cur]=min(Thakur[x],Thakur[y]);
     		}
     		else{
     			Roy[cur]=min(Roy[x],Roy[y]);
     			Thakur[cur]=max(Thakur[x],Thakur[y]);
     		}
     	}
     	if(op==0)cout<<Thakur[1]<<"\n";
     	else cout<<Roy[1]<<"\n";
     }
      
      
    	
    	
    	
    	}
    	
    	   
    return 0;
 
}