program AIB2;
var A : array [1..100000] of longint;
    B : array [1..100000] of integer;
    C : array [0..16] of longint;
    D : array [1..100000] of shortint;
    i,j,m,n,p1,p2,S,k : longint;
    x : shortint;
    f,g : text;
    ok : boolean;
function k2c(n:longint):shortint;
begin
k2c := 0;
while n mod 2 = 0 do begin
k2c := k2c+1;
n := n div 2;
end;
end;
function sum(p:longint):longint;
begin
sum := 0;
while p>0 do begin
sum := sum + A[p];
p := p - (p and(not(p-1)));
end;
end;

function min(st,dr:longint):longint;
var m,b : longint;
begin
if st>dr then min := -1
        else begin
                m := (st+dr) div 2;
                b := sum(m);
                if b>S then min := min(st,m-1)
                       else if b<S then min := min(m+1,dr)
                       else min := m;
                end;

end;

begin
C[0] := 1;
for i := 1 to 16 do
C[i] := C[i-1]*2;
assign(f,'aib.in');
reset(f);
assign(g,'aib.out');
rewrite(g);
readln(f,n,m);

for i := 1 to n do
if i mod 2 = 0 then D[i] := k2c(i)
               else D[i] := 0;

for i := 1 to n do
read(f,B[i]);
readln(f);
for i := 1 to n do begin
A[i] := B[i];
for j := 1 to C[D[i]]-1 do
A[i] := A[i]+B[i-j];
end;
for i := 1 to m do begin
read(f,x);
if x=0 then begin
            readln(f,p1,p2);
            while p1<=n do begin
            A[p1] := A[p1] + p2;
            p1 := p1+(p1 and(not(p1-1)));
            end;
            end
else if x=1 then begin
            readln(f,p1,p2);
            writeln(g,sum(p2)-sum(p1-1));
            end
else begin
     readln(f,S);
     writeln(g,min(1,n));
     end;
end;
close(f);
close(g);
end.