var c:array[1..100000] of longint;
    i,n,m,x,a,b,d:longint;
procedure adaug(a,b:longint);
    var p:longint;
    begin
      p:=a;
      while p<=n do
        begin
          inc(c[p],b);
          p:=p+(p and(not(p-1)));
        end;
    end;
function calc(x:longint):longint;
     var p,s:longint;
     begin
       p:=x;s:=0;
       while p<>0 do
          begin
            inc(s,c[p]);
            p:=p-(p and(not(p-1)));
          end;
       calc:=s;
    end;

function min(st,dr,b:longint):longint;
    var m,s:longint;
    begin
      if st>dr then min:=-1
          else
            begin
              m:=(st+dr) div 2;
              s:=calc(p);
              if s>b then min:=min(st,m-1,b)
                 else if s<b then min:=min(m+1,dr,b)
                    else min:=m;
            end;
    end;

begin
assign(input,'aib.in'); reset(input);
assign(output,'aib.out'); rewrite(output);
readln(n,m);
for i:=1 to n do  begin  read(x); adaug(i,x); end;

for i:=1 to m do
  begin
    read(a);
    if a=0 then
        begin
          read(b,d);
          adaug(b,d);
        end
            else if a=1 then
              begin
                read(b,d);
                writeln(calc(d)-calc(b-1));
              end
                      else
                    begin
                      read(b);
                      d:=min(1,n,b);
                      writeln(d);
                    end;
  end;
close(input);
close(output);
end.