program aib;
type
tabel=array[0..100001] of longint;
buf=array[0..1 shl 17] of char;
var
arb:tabel; ff1,ff2:buf;
n,m,i,j,tip,x,y,rez,sol,st,dr,mm:longint;
f1,f2:text;
function lsb(x:longint):longint;
begin lsb:=(x and (-x)); end;
procedure update(pos,val:longint);
var i:longint;
begin
i:=pos;
while i<=n do begin
arb[i]:=arb[i]+val;
i:=i+lsb(i);
end;
end;
function query(x:longint):longint;
var sol,i:longint;
begin
i:=x; sol:=0;
while i>0 do begin
sol:=sol+arb[i];
i:=i-lsb(i);
end;
query:=sol;
end;
begin
assign (f1,'aib.in');
assign (f2,'aib.out');
reset (f1);
rewrite (f2);
settextbuf(f1,ff1);
settextbuf(f2,ff2);
readln (f1,n,m);
for i:=1 to n do begin read (f1,x); update(i,x); end;
for i:=1 to m do begin
read (f1,tip);
if tip=0 then begin read (f1,x,y); update(x,y); end else
if tip=1 then begin
read (f1,x,y);
writeln (f2,query(y)-query(x-1));
end else begin
read (f1,x); sol:=-1; st:=1; dr:=n;
while st<=dr do begin
mm:=(st+dr) div 2; rez:=query(mm);
if rez=x then begin
sol:=mm; dr:=mm-1;
end else
if rez>x then dr:=mm-1 else st:=mm+1;
end;
writeln (f2,sol);
end;
readln (f1);
end;
close (f1);
close (f2);
end.