program arbore_indexat_binar;
var a,v:array[1..100100] of integer;
     i,j,n,m,s2,s,t,x,y,st,dr,m1,s1:integer;
     f,g:text;
     ok:boolean;
function bit(x:integer):integer;
begin
bit:=(x and (-x));
end;

procedure adauga(p,x:integer);
begin
while (p<=n) do
begin
 v[p]:=v[p]+x;
 p:=p+bit(p);
end;
end;

function suma(x:integer):integer;
begin
suma:=0;
while (x>0) do
begin
 suma:=suma+v[x];
 x:=x-bit(x);
end;
end;
begin
assign(f,'aib.in');
assign(g,'aib.out');
rewrite(g);
reset(f);
readln(f,n,m);
for j:=1 to n do
 begin
  read(f,a[j]);
 end;
for i:=1 to n do adauga(i,a[i]);
for i:=1 to m do
 begin
  read(f,t);
  if (t=0) then
   begin
    readln(f,x,y);
    adauga(x,y);
   end
   else
    if (t=1) then
     begin
      readln(f,x,y);
      s1:=0;
      s2:=0;
      x:=x-1;
      s1:=suma(y);
      s2:=suma(x);
      s:=s1-s2;
      writeln(g,s);
     end
     else
      if (t=2) then
      begin
       readln(f,x);
       st:=1;
       dr:=n;
       ok:=false;
       while (st<=dr) do
       begin
       m1:=(st+dr) div 2;
       s1:=0;
       s1:=suma(m1);
       if (s1=x) then
       begin
        writeln(g,m1);
        st:=n+1;
        ok:=true;
       end
       else
        if (s1>x) then dr:=m1-1
        else
         st:=m1+1;
     end;
     if (ok=false) then writeln(g,' ');
   end;
  end;
close(f);close(g);
end.