program arbori_indexati_binar;
const fi='aib.in';
       fo='aib.out';
var v:array[1..100000] of longint;
   bufin,bufout:array[1..65000] of byte;
   n, m, i, j, c, x, y, k, sum1, sum2:longint;
   f,g:text;
procedure ad(a,b:longint);
var nrz:longint;
begin
v[a]:=v[a]+b;
nrz:=(a xor (a-1))and a;
if a+nrz<=n then
ad(a+nrz,b);
end;
procedure sum(a:longint; var s:longint);
var nrz:longint;
begin
s:=s+v[a];
nrz:=(a xor (a-1))and a;
if a-nrz>0 then
sum(a-nrz,s);
end;
procedure cautbin(a,b:longint);

var m,su:longint;
begin
if a<=b then
  begin
  m:=(a+b) div 2;
  su:=0;
  sum(m,su);
  if x<=su then
    begin
    if x=su then k:=m;
    cautbin(a,m-1)
    end
    else
    begin
    cautbin(m+1,b);
    end;
    end;
    end;
begin


assign(f,fi);
reset(f);
settextbuf(f,bufin);
assign(g,fo);
rewrite(g);
settextbuf(g,bufout);
read(f,n,m);
for i:=1 to n do
   begin
   read(f,x);
   ad(i,x);
   end;
for i:=1 to m do
  begin
  read(f,c);
  case c of
  1:begin
     readln(f,x,y);
     sum1:=0;
     sum2:=0;
     if x<>1 then sum(x-1,sum1);
     sum(y,sum2);
     writeln(g,sum2-sum1);
     end;
  0:begin
      readln(f,x,y);
      ad(x,y);
      end;
  2:begin
  readln(f,x);
  k:=-1;
  cautbin(1,n);
  writeln(g,k);
  end;
  end;
  end;
  close(f);
  close(g);




end.