var v:array[1..250000] of longint;
n,i,x,m,a,b,c,s:longint;
f,g:text;
procedure update(poz,val,lo,hi,nr:longint);
          var mid:longint;
          begin
          if lo=hi then
             inc(v[nr],val)
          else
              begin
              mid:=lo+(hi-lo) shr 1;
              if poz<=mid then
                 update(poz,val,lo,mid,nr*2)
              else
                  update(poz,val,mid+1,hi,nr*2+1);
              v[nr]:=v[nr]+val;
              end;
          end;
procedure sum(x,y,lo,hi,nr:longint);
          var mid:longint;
          begin
          if (x<=lo) and (hi<=y) then
             s:=s+v[nr]
          else
              begin
              mid:=lo+(hi-lo) shr 1;
              if x<=mid then
                 sum(x,y,lo,mid,nr*2);
              if y>mid then
                 sum(x,y,mid+1,hi,nr*2+1);
              end;
          end;
procedure pr3(si,lo,hi,nr:longint);
          var mid:longint;
          begin
          if lo=hi then
             begin
             if si+v[nr]=b then
                s:=lo
             else
                 s:=-1;
             end
          else
              begin
              mid:=lo+(hi-lo) shr 1;
              if si+v[2*nr]>=b then
                 pr3(si,lo,mid,nr*2)
              else
                  pr3(si+v[nr*2],mid+1,hi,nr*2+1);
              end;
          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,1,n,1);
    end;
readln(f);
for i:=1 to m do
    begin
    read(f,a,b);
    case a of
         0:begin
           readln(f,c);
           update(b,c,1,n,1);
           end;
         1:begin
           s:=0;
           readln(f,c);
           sum(b,c,1,n,1);
           writeln(g,s);
           end;
         2:begin
           readln(f);
           pr3(0,1,n,1);
           writeln(g,s);
           end;
         end;
    end;
close(f);close(g);
end.