Program Aib;
 var f,g:text; i,n,m,x,y:longint;
     a:array[1..100000]of longint;
     key:byte;
 function next (x:longint):longint;
  var y:longint;
  begin
   y:=1;
   while (x mod 2)=0 do begin
     y:=y*2;
     x:=x div 2;
   end;
   exit (y);
  end;
 procedure sum (x,y:longint);
  begin
   while (x<=n) do begin
     a[x]:=a[x]+y;
     x:=x+next (x);
   end;
  end;
 function suma (x:longint):longint;
  var z:longint;
  begin
   if x=1 then exit (a[1]);
   z:=0;
   while x>1do begin
     inc (z,a[x]);
     x:=x-next (x);
   end;
   exit (z);
  end;
 function sum_int (x,y:longint):longint;
  begin
   exit (suma (y)-suma (x-1));
  end;
 procedure cauta (x:longint);
  var l,r,m:longint;
  begin
   l:=1; r:=n;
   while r>=l do begin
     m:=(l+r) div 2;
     if suma ((l+r) div 2)<x then l:=m+1 else
       if suma ((l+r) div 2)>x then r:=m-1 else begin
         writeln (g,(l+r) div 2);
         exit;
       end;
   end;
   writeln (g,-1);
  end;
 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);
    sum (i,x);
  end;
  for i:=1 to m do begin
    read (f,key);
    case key of
      0: begin
           readln (f,x,y);
           sum (x,y);
         end;
      1: begin
           readln (f,x,y);
           writeln (g,sum_int (x,y));
         end;
      2: begin
           readln (f,x);
           cauta (x);
         end;
    end;
  end;
  close (f); close (g);
 end.