var c:array[1..100000] of longint;
    w,i,n,m,x,a,b,d:longint;
function nr_zero(r:longint):longint;
    var q:longint;
    begin
      q:=0;
      while r and 1=0 do
        begin
          inc(q);
          r:=r shr 1;
        end;
      nr_zero:=q;
    end;
procedure adaug(a,b:longint);
    var k,p,q:longint;
    begin
      if a<=n then
         begin
           c[a]:=c[a]+b;
           k:=nr_zero(a);
           p:=1; p:=p shl k;
           adaug(a+p,b);
         end;
    end;
function calc(x:longint):longint;
     var p,k:longint;
     begin
       if x<>0 then
         begin
           k:=nr_zero(x);
           p:=1; p:=p shl k;
           calc:=c[x]+calc(x-p);
         end else calc:=0;
     end;

begin
assign(input,'aib.in'); reset(input);
assign(output,'aib.out'); rewrite(output);
readln(n,m);
for i:=1 to n do c[i]:=0;
for i:=1 to n do
   begin
    read(x);
    adaug(i,x);
  end;
for i:=1 to m do
  begin
    read(a);
    if a=0 then
        begin
          read(b,d);
          adaug(b,d);
        end
          else if a=1 then
              begin
                read(b,d);
                writeln(calc(d)-calc(b-1));
              end
                 else
                    begin
                      read(b);
                      d:=1;
                      while (calc(d)<>b)and(d<n) do inc(d);
                      if calc(d)<>b then writeln('-1')
                                    else writeln(d);
                    end;
  end;
close(input);
close(output);
end.