type    vector=array[0..15000] of longint;
var     a,v:vector;
        n,m,i,j,x,y:longint;
        f,t:text;

function zer(t:longint):longint;
var     i,j:longint;
begin
  i:=0;
  while t mod 2=0 do
    begin
      inc(i);
      t:=t div 2;
    end;
  if i=0 then zer:=1 else
    begin
      zer:=1;
      for j:=1 to i do
      zer:=zer*2;
    end;
end;

function suma(p:longint; a:vector):longint;
var     t:longint;
begin
  suma:=0;
  if p>0 then
  begin
  t:=zer(p);
  while p-t>=0 do
    begin
      suma:=suma+a[p];
      dec(p,t);
      if p>0 then t:=zer(p);
    end;
  end;
end;

procedure init;
var     i,j,k:longint;
begin
  for i:=1 to n do
    v[i]:=0;
  for i:=1 to n do
    v[i]:=a[i]+suma(i-1,v)-suma(i-zer(i),v);
end;

procedure modifica(x,y:longint);
var t:longint;
begin
  t:=zer(x);
  v[x]:=v[x]-y;
  while x+t<=n do
    begin
      inc(x,t);
      t:=zer(x);
      v[x]:=v[x]-y;
    end;
end;

begin
  assign(f,'datorii.out');
  rewrite(f);
  assign(t,'datorii.in');
  reset(t);
  readln(t,n,m);
  for i:=1 to n do
    read(t,a[i]);
  init;
    for i:=1 to m do
    begin
      readln(t,j,x,y);
      if j=1 then writeln(f,suma(y,v)-suma(x-1,v))
      else modifica(x,y);
    end;
  close(t);
  close(f);
end.