type
  ab=record
    x,y:longint;
  end;
var
  f,q:array[0..300000] of ab;
  flag:array[0..500] of boolean;
  tmp,g:ab;
  n,i,max_r,min_r:longint;

procedure swap(var x,y:ab);
var
  tmp:ab;
begin
  tmp:=x;
  x:=y;
  y:=tmp;
end;

procedure insert_max(tmp:ab);
var
  i:longint;
begin
  inc(max_r);
  q[max_r]:=tmp;
  i:=max_r;
  while (i>1) and (q[i].y>q[i shr 1].y) do
    begin
      swap(q[i],q[i shr 1]);
      i:=i shr 1;
    end;
end;

procedure insert_min(tmp:ab);
var
  i:longint;
begin
  inc(min_r);
  f[min_r]:=tmp;
  i:=min_r;
  while (i>1) and (f[i].y<f[i shr 1].y) do
    begin
      swap(f[i],f[i shr 1]);
      i:=i shr 1;
    end;
end;

procedure change_max(x:longint);
var
  max,l_,r_:longint;
begin
  max:=x;
  l_:=x shl 1;
  r_:=l_+1;
  if (l_<=max_r) and (q[l_].y>q[max].y) then max:=l_;
  if (r_<=max_r) and (q[r_].y>q[max].y) then max:=r_;
  if max<>x then
    begin
      swap(q[x],q[max]);
      change_max(max);
    end;
end;

procedure change_min(x:longint);
var
  min,l_,r_:longint;
begin
  min:=x;
  l_:=x shl 1;
  r_:=l_+1;
  if (l_<=min_r) and (f[l_].y<f[min].y) then min:=l_;
  if (r_<=min_r) and (f[r_].y<f[min].y) then min:=r_;
  if min<>x then
    begin
      swap(f[x],f[min]);
      change_min(min);
    end;
end;

function get_max():ab;
var
  res:ab;
begin
  res:=q[1];
  q[1]:=q[max_r];
  dec(max_r);
  if max_r>1 then change_max(1);
  exit(res);
end;

function get_min():ab;
var
  res:ab;
begin
  res:=f[1];
  f[1]:=f[min_r];
  dec(min_r);
  if min_r>1 then change_min(1);
  exit(res);
end;

begin
  fillchar(q,sizeof(q),0);
  fillchar(f,sizeof(f),0);
  fillchar(flag,sizeof(flag),true);
  max_r:=0;
  min_r:=0;
  read(n);
   while n<>0 do
    begin
      case n of
        1:begin
            read(tmp.x,tmp.y);
            flag[tmp.y]:=false;
            insert_max(tmp);
            insert_min(tmp);
          end;
        2:begin
            g:=get_max();
            while (g.y<>0) and (flag[g.y]) do g:=get_max();
            writeln(g.x);
            flag[g.y]:=true;
            if q[1].y=0 then max_r:=0;
          end;
        3:begin
            g:=get_min();
            while (g.y<>0) and (flag[g.y]) do g:=get_min();
            writeln(g.x);
            flag[g.y]:=true;
            if f[1].y=0 then min_r:=0;
          end;
      end;
      read(n);
    end;
end.