var c:array[1..100000] of longint;
        i,n,m,x,a,b,d,s:longint;
    f,g:text;
    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 p,k:longint;
      begin
         if st>dr then min:=-1
             else
               begin
                p:=(st+dr) div 2;
                k:=calc(p);
                 if k>b then min:=min(st,p-1,b)
                    else if k<b then min:=min(p+1,dr,b)
                      else min:=p;
              end;
       end;

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

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