var     a:array[1..100000,0..16] of longint;
        n,m,i,j,l,c,x,y,p,t,maxim:longint;
        f,g:text;

function max(var a,b:longint):longint;
begin
  if a>b then max:=a else max:=b;
end;

begin
  assign(f,'arbint.in');
  assign(g,'arbint.out');
  reset(f);
  rewrite(g);
  readln(f,n,m);
  i:=1;
  p:=1;
  while i*2 <n do begin inc(p); i:=i*2; end;

  for i:=1 to n do
    read(f,a[i,0]);

  for i:=1 to p do
  for j:=1 to n do
    if j + (1 shl (i-1))>n then break else
    a[j,i]:=max(a[j,i-1],a[j+(1 shl (i-1)),i-1]);

  for i:=0 to p do
    begin
  for j:=1 to n do
    write(a[j,i],' ');
    writeln;
    end;
    readln;
  for i:=1 to m do
    begin
      readln(f,c,x,y);
      if c=0 then
        begin
          t:=0;
          j:=y-x;
          while 1 shl (t+1)<=j do inc(t);
          maxim:=max(a[x,t],a[y-(1 shl t)+1,t]);
          writeln(g,max(a[y,0],maxim));
        end else
        begin
          a[x,0]:=y;
          for j:=1 to p do
            begin
              //a[x,j]:=max(a[x+(1 shl (j-1)),j-1],y);
              //if x-(1 shl (j-1))+1>0 then
              for l:=x-(1 shl (j-1))-1 to x do
                if l>0 then
                a[l,j]:=max(a[l,j-1],a[l+(1 shl (j-1)),j-1]);
            end;
          for l:=0 to p do
    begin
  for j:=1 to n do
    write(a[j,l],' ');
    writeln;
    end;
    readln;
        end;
    end;
  close(g);
end.