var     a,v,b,c:array[0..15000] of longint;
        e:array[1..100000] of string;
        n,m,i,j,x,y:longint;
        f,t:text;
        s,ss:string[200];
        poz:integer;
        cod:integer;

function suma(p:longint):longint;
begin
  suma:=0;
  while p>0 do
    begin
      suma:=suma+v[p];
      dec(p,c[b[p]]);
    end;
end;

procedure modifica(x,y:longint);
begin
  while x<=n do
    begin
      v[x]:=v[x]-y;
      inc(x,c[b[x]]);
    end;
end;

begin
  assign(f,'datorii.out');
  rewrite(f);
  assign(t,'datorii.in');
  reset(t);
  readln(t,n,m);
   poz:=0;
      while poz<n do
        begin
          inc(poz);
          read(t,s);
          for i:=1 to length(s) do
          if s[i]=' ' then inc(poz) else a[poz]:=a[poz]*10+ord(s[i])-ord('0');
        end;

  for i:=1 to 10 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 10 do
    c[i]:=c[i-1]*2;

  for i:=1 to n do
    v[i]:=a[i]+suma(i-1)-suma(i-c[b[i]]);
  readln(t);
  for i:=1 to m do
    readln(t,e[i]);
  for i:=1 to m do
    begin
      poz:=3;
      while e[i][poz]<>' ' do inc(poz);
      val(e[i][1],j,cod);
      val(copy(e[i],3,poz-3),x,cod);
      val(copy(e[i],poz+1,length(e[i])-poz),y,cod);
      if j=1 then writeln(f,suma(y)-suma(x-1))
      else modifica(x,y);
    end;
  close(t);
  close(f);
end.