program arbori_indexati_binar;
  var f1,f2:text;
      m,n,i,p,x,y:longint;
      a:array [1..100000] of longint;
      op:byte;
      bufin,bufout:array [1..100000] of byte;
procedure zero;
  begin
    while x<=n do
      begin
        a[x]:=a[x]+y;
        x:=x+x and -x;
      end;
  end;
procedure one;
  var s1,s2:longint;
  begin
    s2:=0;s1:=0;
    x:=x-1;
    while x>0 do
      begin
        s1:=s1+a[x];
        x:=x-x  and -x;
      end;
    while y>0 do
      begin
        s2:=s2+a[y];
        y:=y-y and -y;
      end;
    writeln(f2,s2-s1);
  end;
procedure two;
  var z:longint;
  begin
    z:=p;
    if (z=n) and (x=a[z]) then writeln(f2,z)
      else
        begin
          z:=z div 2;
          while x<>a[z] do
            begin
              if x>a[z] then begin x:=z-a[z]; z:=z+(z and -z)div 2; end
                        else z:=z-(z and -z)div 2;
            end;
          writeln(f2,z);
        end;
  end;
begin
  assign(f1,'aib.in');
  reset(f1);
  assign(f2,'aib.out');
  rewrite(f2);
  settextbuf(f1,bufin);
  settextbuf(f2,bufout);
  readln(f1,n,m);
  for i:=1 to n do read(f1,a[i]);
  readln(f1);
  p:=2;
  while p<=n do
    begin
      i:=p;
      while i<=n do
        begin
          a[i]:=a[i]+a[i-p div 2];
          i:=i+p;
        end;
      p:=p*2;
    end;
  for i:=1 to m do
    begin
      read(f1,op,x);
      if op=0 then begin readln(f1,y);zero;end
              else if op=1 then begin readln(f1,y);one;end
                           else begin readln(f1);two;end;
    end;
  close(f1);
  close(f2);
end.