program datorii;   
var B : array [1..15000] of longint;   
    A : array [1..15000] of integer;   
    C : array [0..13] of integer;   
    D : array [1..15000] of shortint;   
    f,g : text;   
    n,x,p1,p2 : integer;   
    i,m : longint;   
  
function k2c(n:integer):shortint;   
begin  
k2c := 0;   
while n mod 2 = 0 do begin  
k2c := k2c+1;   
n := n div 2;   
end;   
end;   
  
  
function k2(n:integer):integer;   
begin  
if n=0 then k2 := 1  
else  
if n=1 then k2 := 2  
       else if n mod 2 = 0 then k2 := sqr(k2(n div 2))   
                           else k2 := 2*sqr(k2(n div 2))   
end;   
  
procedure build;   
var i,j : integer;   
begin  
  
for i := 1 to n do begin  
B[i] := A[i];   
  
for j := 1 to C[D[i]]-1 do  
B[i] := B[i]+A[i-j];   
end;   
end;   
  
procedure update(poz,val : integer);   
begin  
  
while poz<=n do begin  
B[poz] := B[poz]-val;   
poz := poz+C[D[poz]];   
end;   
end;   
  
function sum(p:integer):longint;   
begin  
sum := 0;   
while p>0 do begin  
sum := sum + B[p];   
p := p-C[D[p]];   
end;   
end;   
  
  
begin  
assign(f,'datorii.in');   
reset(f);   
assign(g,'datorii.out');   
rewrite(g);   
  
readln(f,n,m);   
  
for i := 1 to n do  
read(f,A[i]);   
readln(f);   
  
C[0] := 1;   
for i := 1 to 13 do  
C[i] := k2(i);   
  
for i := 1 to n do  
D[i] := k2c(i);   
  
  
build;   
  
  
for i := 1 to m do begin  
readln(f,x,p1,p2);   
if x=1 then writeln(g,sum(p2)-sum(p1-1))   
else update(p1,p2);   
end;   
  
close(f);   
close(g);   
  
end.