#include <cstdio>
#include <cstring>
FILE *f=fopen("arbint.in","r"),*g=fopen("arbint.out","w");
int n,m,st[400],dr[400],mx[400],a[100005],buc[100005],b[100005],e[100005],t[100005],k,maxx[100005],p=0;
char c[900005];
void Read(); void Solve(); void Update(int x); void Query(int x,int y);
void Parse()
{ char c[1000005],ch;
 int i=0,nr=0,k=0,len,j;
  fscanf(f,"%c",&ch);
   fgets(c,1000000,f);
    len=strlen(c);
  for(i=0;i<len;i++)
  if (c[i]>=48 && c[i]<=57) nr=nr*10+(c[i]-48);
  else {k++; a[k]=nr; nr=0;}
  for(j=1;j<=m;j++)
  { k=0; nr=0;
    fgets(c,60,f);
    len=strlen(c);
  for(i=0;i<len;i++)
  if (c[i]>=48 && c[i]<=57) nr=nr*10+(c[i]-48);
  else {k++; if (k==1) t[j]=nr; else if (k==2) b[j]=nr; else e[j]=nr; nr=0;}

  }
}
void Read()
{ int i,j,max1=0,ch;
  fscanf(f,"%d %d",&n,&m);
   Parse();
  k=1;
   while(k*k<=n) k++;
  k--;

   for(i=1;i<=k;i++)
    {st[i]=dr[i-1]+1; dr[i]=st[i]+k-1;
     max1=-1;
      for(j=st[i];j<=dr[i];j++)
       {if (a[j]>max1) max1=a[j];
       buc[j]=i;
       }
     mx[i]=max1;
    // cout<<st[i]<<" "<<dr[i]<<" "<<mx[i]<<"\n";
     }
}
void Solve()
{ int i;
  for(i=1;i<=m;i++)
  { if (!t[i]) {Query(b[i],e[i]); }
     else {a[b[i]]=e[i]; Update(b[i]); }
  }
}
void Update(int x)
{ int i,v,max2;
  v=buc[x];
  if (!buc[x]) return;
  max2=-1;
  for(i=st[v];i<=dr[v];i++)
    if (a[i]>max2) max2=a[i];
  mx[v]=max2;
}
void Query(int x,int y)
{ int max3=-1,i,mnv=y,mxv=x;
    //cout<<mx[2]<<" "<<y<<" "<<st[buc[y]]<<" "<<dr[buc[y]]<<"\n";
    for(i=1;i<=k;i++)
    if (x<=st[i] && dr[i]<=y)
       { if (mx[i]>max3) max3=mx[i];
         if  (st[i]<mnv) mnv=st[i];
         if  (dr[i]>mxv) mxv=dr[i];
       }

    for(i=x;i<=mnv;i++) if (a[i]>max3) max3=a[i];
    for(i=mxv;i<=y;i++) if (a[i]>max3) max3=a[i];
fprintf(g,"%d\n",max3);
}
void Write()
{ int i,j,ord=0;
  char num[15];
  memset(c,0,sizeof(c));
  p=-1;

  for(i=1;i<=m;i++)
  { ord=-1;
    while(maxx[i]) {ord++; num[ord]=(char) (maxx[i]%10)+48; maxx[i]/=10;}
     for(j=ord;j>=0;j--)
     {p++; c[p]=num[j];}
    p++; c[p]='\n';
  }
fprintf(g,"%s",c);
}
int main()
{ Read();
  Solve();
  //Write();
    return 0;
}