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