program pascal;
var f,g:text; aib:array[1..150000] of longint; x,i,j,n,m,t1,t2,y,r:longint;

 procedure up(i,x:longint);
 begin
 while i<=n do
   begin
   aib[i]:=aib[i]+x;
   i:=i+(i xor (i-1) and i);
   end;
 end;

 function sum(i:longint):longint;
 begin
 r:=0;
 while i>0 do
   begin
   r:=r+aib[i];
   i:=i-(i xor (i-1) and i);
   end;
 sum:=r;
 end;

 function caut(st,dr:longint):longint;
 begin
 m:=sum((st+dr) div 2);
 if st>=dr then
      begin
      if m=x then caut:=st
             else caut:=-1;
      end
      else
      if x<=m then caut:=caut(st,(st+dr) div 2)
              else caut:=caut((st+dr)div 2+1,dr);

 end;

 procedure citire;
 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);
   up(i,x);
   end;
 for j:=1 to m do
     begin
     read(f,x);
     if x=0 then
            begin
            read(f,x,y);
            up(x,y);
            end  else
     if x=1 then
            begin
            read(f,x,y);
            t1:=sum(x-1);
            t2:=sum(y);
            writeln(g,t2-t1);
            end else
     if x=2 then
            begin
            read(f,x);
            writeln(g,caut(1,n));
            end;
     end;
 end;

begin
citire;
close(f);
close(g);
end.