var aib:array[1..100000]of longint;
    x,n,m,i,j,a,b:longint;
    f,fo:text;
    tip:byte;
function zero(x:longint):longint;
begin
zero:=(x xor (x-1))and x
end;

procedure add(x:word;p:longint);
var i:longint;
begin
i:=p;
while i<=n do
 begin
  inc(aib[i],x);
  inc(i,zero(i))
 end
end;

function suma(p:longint):longint;
var s,i:longint;
begin
s:=0;
i:=p;
while i>0 do
 begin
  inc(s,aib[i]);
  dec(i,zero(i));
 end;
suma:=s
end;
function querry(k:longint):longint;
var st,dr,mij,s:longint;
begin
st:=0;dr:=n+1;
while dr-st>1 do
 begin
  mij:=st+(dr-st)div 2;
  s:=suma(mij);
  if s<k then
   st:=mij
         else
   dr:=mij
 end;
s:=suma(dr);
if (dr=n+1)or(s<>k)then
 querry:=-1
                   else
 querry:=dr
end;

begin
assign(f,'aib.in');
assign(fo,'aib.out');
reset(f);
readln(f,n,m);
for j:=1 to n do
 begin
  read(f,x);
  add(x,j)
 end;
readln(f);
rewrite(fo);
for j:=1 to m do
 begin
  read(f,tip,a);
  if tip<>2 then readln(f,b)
            else readln(f);
  case tip of
   0:add(b,a);
   1:writeln(fo,suma(b)-suma(a-1));
   2:writeln(fo,querry(a));
  end;
 end;
close(fo);
close(f);
end.