var v:array[1..100000] of longint;
m,n,i,x,y,z,a,b,mid,suma:longint;
f,g:text;
k:boolean;
function zeros(p:longint):longint;
         begin
         zeros:=p and ((p-1) xor p);
         end;
procedure update(poz,val:longint);
          begin
          repeat
                inc(v[poz],val);
                inc(poz,zeros(poz));
          until poz>n;
          end;
function sum(hi:longint):longint;
         var s:longint;
         begin
         s:=0;
         repeat
               inc(s,v[hi]);
               dec(hi,zeros(hi));
         until hi<1;
         sum:=s;
         end;
begin
assign(f,'aib.in');
assign(g,'aib.out');
reset(f);rewrite(g);
readln(f,n,m);
for i:=1 to n do
    begin
    read(f,x);
    update(i,x);
    end;
for i:=1 to m do
    begin
    read(f,x);
    case x of
         0:begin
           readln(f,y,z);
           update(y,z);
           end;
         1:begin
           readln(f,y,z);
           writeln(g,sum(z)-sum(y-1));
           end;
         2:begin
           readln(f,y);
           a:=1;b:=n;
           k:=false;
           while a<=b do
                 begin
                 mid:=a+(b-a) shr 1;
                 suma:=sum(mid);
                 if suma>=y then
                    begin
                    if suma=y then
                       k:=true;
                    b:=mid-1;
                    end
                 else
                     a:=mid+1;
                 end;
           if k=false then
              writeln(g,-1)
           else
               writeln(g,b+1);
           end;
         end;
    end;
close(f);close(g);
end.