var x,y,n,m,k,i,op,sum:longint;
    s:string;
    a:array[0..264000] of longint;

procedure adauga(nod,st,dr:longint);
  var mij:longint;
  begin
    if st>=dr then begin
        a[nod]:=a[nod]+y;
      {  exit;                                   }
    end else begin
        mij:=(st+dr) shr 1;
        if x<=mij then adauga(nod shl 1,st,mij) else
                adauga((nod shl 1)+1,mij+1,dr);
        a[nod]:=a[nod]+y;
    end;
  end;

procedure suma(nod,st,dr:longint);
  var mij:longint;
  begin
    if (x<=st) and (y>=dr) then sum:=sum+a[nod]
    else begin
      mij:=(st+dr) shr 1;
      if x<=mij then suma(nod shl 1,st,mij);
      if y>mij then suma((nod shl 1)+1,mij+1,dr);
    end;
  end;

procedure suma2(nod,st,dr:longint);
  var mij:longint;
  begin
    if st>=dr then begin
        if x=a[nod] then k:=st else k:=-1;
        exit;
        end
    else

      mij:=(st+dr) shr 1;
      if x>a[nod shl 1] then begin
        x:=x-a[nod shl 1];
        suma2((nod shl 1)+1,mij+1,dr);
      end else begin
        suma2(nod shl 1,st,mij);
      end;
  end;

begin
  assign(input,'aib.in');
  reset(input);
  assign(output,'aib.out');
  rewrite(output);

  readln(n,m);
  y:=0;
  x:=0;
  while (not(eoln(input))) do begin
    read(s);
    for k:=1 to length(s) do begin
      if s[k]=' ' then begin
        x:=x+1;
        adauga(1,1,n);
        y:=0;
      end else y:=y*10+(ord(s[k])-48);
    end;
  end;
  inc(x);
  if s[k]<>' ' then adauga(1,1,n);

  for i:=1 to m do begin
    read(op);
    if op=2 then readln(x) else readln(x,y);
    if op=0 then adauga(1,1,n)
    else if op=1 then begin
        sum:=0;
        suma(1,1,n);
        writeln(sum);
    end else begin
       k:=0;
       suma2(1,1,n);
       writeln(k);
    end;
  end;

  close(input);
  close(output);
end.