Program aib;
 var w,aux:array [0..100001] of longint;
     k:array [1..100000] of byte;
     i,n,m,t,a,b,pos:longint;
     b1:array [1..1 shl 15] of char;
     fi,fo:text;
procedure gen;
 var nr,i,x:longint;
begin
 for i:=1 to 100000 do begin
                       nr:=0; x:=i;
                        while x and 1=0 do begin inc(nr); x:=x shr 1; end;
                       k[i]:=nr;
                       end;
end;
procedure change(a,b:longint);
begin
 while a<=n do begin aux[a]:=aux[a]+b; a:=a+(1 shl k[a]); end;
end;
function sum(x:longint):longint;
 var s:longint;
begin
  s:=0;
 while x>0 do begin s:=s+aux[x]; x:=x-(1 shl k[x]); end;
  sum:=s;
end;
procedure cauta(x:longint);
 var l,r,mid,p:longint;
begin
 l:=1; r:=n; pos:=-1;
  while (l<=r) and (pos=-1) do begin
                                mid:=(l+r) div 2; p:=sum(mid);
                                if p>x then r:=mid-1
                                else if p<x then l:=mid+1
                                 else pos:=mid;
                                end;
end;
begin
 assign(fi,'aib.in');
  assign(fo,'aib.out');
 settextbuf(fi,b1);
 reset(fi); rewrite(fo); readln(fi,n,m);
  for i:=1 to n do begin
                    read(fi,w[i]); w[i]:=w[i]+w[i-1];
                    end;  readln(fi);  gen;
  for i:=1 to n do aux[i]:=w[i]-w[i-(1 shl k[i])];
   for i:=1 to m do begin
                    read(fi,t);
                     if t=0 then begin readln(fi,a,b); change(a,b); end
                      else if t=1 then begin readln(fi,a,b); writeln(fo,sum(b)-sum(a-1)); end
                       else begin readln(fi,a); cauta(a); writeln(fo,pos); end;
                     end;
  close(fo);
end.