var     i,j,n,m,c,x,y,p:longint;
        f1,f2:text;
        s:string;
        a,v:array[1..100000]of longint;

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

procedure schimba(x,y:longint);
var     i:longint;
begin
  i:=x;
  while i<=n do
    begin
      v[i]:=v[i]+y;
      i:=i+(i xor (i and (i-1)));
    end;
end;

function suma(p:longint):longint;
begin
  suma:=0;
  while p>0 do
    begin
      suma:=suma+v[p];
      p:=p-(p xor (p and (p-1)));
    end;
end;

function poz(p:longint):longint;
var     i,j,s:longint;
begin
  s:=0;
  i:=1;
  j:=0;
  while (s<p)and(j<=n) do
    begin
      while (s+v[j+i*2]<=p)and(j+i*2<=n) do i:=i*2;
      s:=s+v[j+i];
      j:=j+i;
      i:=1;
    end;

  if s=p then poz:=j
  else poz:=-1;
end;

begin
  assign(f1,'aib2.in');
  reset(f1);
  assign(f2,'aib.out');
  rewrite(f2);
  readln(f1,n,m);
  p:=1;
  while p<n do
    begin
      readln(f1,s);
      for i:=1 to length(s) do
        if s[i]=' ' then inc(p) else a[p]:=a[p]*10+ord(s[i])-ord('0');
      if length(s)=254 then inc(p);
    end;

  init;

{  for i:=1 to 4808 do
    sum:=sum+a[i];
  writeln(f2,sum);}

  for i:=1 to m do
    begin
      read(f1,c);
      if c=0 then
        begin
          readln(f1,x,y);
          schimba(x,y);
        end;
      if c=1 then
        begin
          readln(f1,x,y);
          writeln(f2,suma(y)-suma(x-1));
        end;
      if c=2 then
        begin
          readln(f1,x);
          writeln(f2,poz(x));
        end;
    end;

  close(f1);
  close(f2);
end.