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

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

procedure modifica(x,y:longint);
var t:longint;
begin
  t:=c[b[x]];
  v[x]:=v[x]-y;
  while x+t<=n do
    begin
      inc(x,t);
      t:=c[b[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]);

  for i:=1 to n do
    if b[i]=0 then
      begin
        j:=i;
          while j<=n do
            begin
              b[j*2]:=b[j]+1;
              j:=j*2;
            end;
      end;

  c[0]:=1;
  for i:=1 to 15 do
    c[i]:=c[i-1]*2;

  for i:=1 to n do
    v[i]:=a[i]+suma(i-1,v)-suma(i-c[b[i]],v);

  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.