var     a:array[1..300000] of longint;
        n,m,i,j,p,x,y,c:longint;
        f,g:text;

procedure modifica(j,p:longint);
begin
  while j<=n do
    begin
      inc(a[j],p);
      j:=j+(j xor ((j-1) and j));
    end;
end;

function suma(j:longint):longint;
begin
  suma:=0;
  while j>0 do
    begin
      inc(suma,a[j]);
      j:=j-(j xor ((j-1) and j));
    end;
end;

function poz(s:longint):longint;
var     i,sc,p:longint;
begin
  i:=0;
  sc:=0;
  p:=0;
  while (sc<s)and (p<n) do
    begin
      i:=0;
      while (sc+a[p+(1 shl (i+1))]<=s) and (p+(1 shl (i+1))<=n) do inc(i);
      sc:=sc+a[p+(1 shl i)];
      p:=p+(1 shl i);
    end;
  if sc=s then poz:=p else poz:=-1;
end;

begin
  assign(f,'aib.in');
  assign(g,'aib.out');
  reset(f);
  rewrite(g);
  readln(f,n,m);
  fillbyte(a,sizeof(a),0);

  for i:=1 to n do
    begin
      read(f,p);
      modifica(i,p);
    end;

  {for i:=1 to n do
    writeln(g,a[i]);}
  readln(f);
  for i:=1 to m do
    begin
      read(f,c);
      if c=0 then
        begin
          readln(f,x,y);
          modifica(x,y);
        end else
      if c=1 then
        begin
          readln(f,x,y);
          writeln(g,suma(y)-suma(x-1));
        end else
        begin
          readln(f,x);
          writeln(g,poz(x));
        end;
    end;
  close(g);
end.