program aib;
  var a:array[1..100000] of longint;
      n,m,i,op,poz,k,val,x,y:longint;
  procedure update(poz,val:longint);
    begin
     while (poz<=n)do
       begin
         a[poz]:=a[poz]+val;
         poz:=poz+(poz and -poz);
       end;
    end;
  function sum(poz:longint):longint;
    var s:longint;
   begin
     s:=0;
     while poz>0 do
      begin
        s:=s+a[poz];
        poz:=poz-(poz and -poz);
      end;
     sum:=s;
   end;

   function  query:longint;
    var st,dr,mij,m:longint;
   begin
     st:=1;
     dr:=n;
     while st<=dr do
       begin
        mij:=(st+dr)div 2;
        m:=sum(mij) ;
        if m>val then dr:=mij-1
          else if m<val then st:=mij+1
            else exit(mij);
        end;
     exit(-1);
   end;
   begin
    assign(input,'aib.in');
    assign(output,'aib.out');
    reset(input);
    rewrite(output);
    readln(n,m);
    for i:=1 to n do
     begin
      read(x);
      update(i,x);
     end;
    for i:=1  to m do
      begin
        read(op);
        if op=0 then begin
            readln(poz,val);
            update(poz,val);
            end;
        if op=1 then begin
            readln(x,y);
            writeln(sum(y)-sum(x-1));
            end;
        if op=2 then begin
            readln(val);
            writeln(query);
            end;
      end;
    close(output);
    close(input);
    end.