{$mode objfpc}
program sdf;
const
fo='';
fi='';
type
hs=record
x,y:integer;
end;
var
f,g:text;
a,b:array[0..1000001]of hs;
c,d:array[0..1000001]of integer;
n,t1,t2:integer;
procedure swap(var x,y:hs);
 var t:hs;
 begin
 t:=x;
 x:=y;
 y:=t;
 end;
procedure swap1(var x,y:integer);
 var t:integer;
 begin
 t:=x;
 x:=y;
 y:=t;
 end;
procedure upheap1(i:integer);
  begin
  if (i<=1)or(a[i].y<=a[i div 2].y) then exit;
   swap1(c[a[i].x],c[a[i div 2].x] );
   swap(a[i],a[i div 2]);
   upheap1(i div 2);
  end;
procedure upheap2(i:integer);
   begin
  if (i<=1)or(b[i].y>=b[i div 2].y) then exit;
  swap1(d[b[i].x],d[b[i div 2].x]);
  swap(b[i],b[i div 2]);
  upheap2(i div 2);
  end;
procedure downheap1(i,k:integer);
var
 t:integer;
   begin
   t:=i*2;
   if (t>k)or((a[i].y>=a[t].y)and(a[i].y>=a[t+1].y)) then exit;
   if a[t].y<a[t+1].y then inc(t);
   swap1(c[a[i].x],c[a[t].x]);
   swap(a[i],a[t]);
   downheap1(t,k);
   end;
procedure downheap2(i,k:integer);
var
 t:integer;
   begin
   t:=i*2;
   if (t>k)or((b[i].y<=b[t].y)and(b[i].y<=b[t+1].y)) then exit;
   if b[t].y>b[t+1].y then inc(t);
   swap1(d[b[i].x],d[b[t].x]);
   swap(b[i],b[t]);
   downheap1(t,k);
   end;
procedure push1(x:hs);
  begin
  inc(t1);
  a[t1]:=x;
  upheap1(t1);
  end;
procedure push2(x:hs);
  begin
  inc(t2);
  b[t2]:=x;
  upheap2(t2);
  end;
function pop1(i:integer):integer;
   begin
   pop1:=a[i].x;
   a[i]:=a[t1];
   c[a[i].x]:=c[a[t1].x];
   dec(t1);
   upheap1(i);
   downheap1(i,t1);
   end;
function pop2(i:integer):integer;
   begin
   pop2:=b[i].x;
   d[b[i].x]:=d[b[t2].x];
   b[i]:=b[t2];
   dec(t2);
   upheap2(i);
   downheap2(i,t2);
   end;
procedure init;
  begin
  t1:=0;
  t2:=0;
  end;
procedure openf;
  begin
  assign(f,fo);
  reset(f);
  assign(g,fi);
  rewrite(g);
  end;
procedure nhap;
  var i,k,k1,k2,n:integer;
  cd:hs;
begin
 repeat
 read(f,k);
 case k of
 1:
   begin
   with cd do
   begin
   readln(f,x,y);
   d[x]:=t1+1;
   c[x]:=t2+1;
   end;
   push1(cd);
   push2(cd);
   end;
 2:
  begin
  readln(f);
  if t1=0 then writeln(g,'0')
  else
  begin
  n:=d[a[1].x];
  writeln(g,pop1(1));
  pop2(n);
  end;
  end;
 3:
  begin
  readln(f);
  if t2=0 then writeln(g,'0')
  else
   begin
   n:=c[b[1].x];
   writeln(g,pop2(1));
   pop1(n);
   end;
  end;
  end;
 until k=0;
end;
procedure closef;
 begin
 close(f);
 close(g);
 end;
begin
openf;
init;
nhap;
closef;
end.

 
const
  fi='';//'b.in';
  fo='';//'b1.out';
  maxn = 445;
  maxnum = 500;
type
  re = record
    gt, p, pos1, pos2: longint;
  end;
var
//  pos1, pos2: array[0..maxn] of longint;
  sl, nheapmin, nheapmax: longint;
  f, f1: text;
  heapmin, heapmax: array[0..maxnum] of longint;
  d: array[0..maxn] of re;
procedure open;
begin
  assign(f, fi);
  reset(f);
  assign(F1, fo);
  rewrite(f1);
end;
 
procedure closefile;
begin
  close(F1);
  close(f);
end;
 
procedure push(sl:longint);
var
  child, parent: longint;
begin
 
  inc(nheapmax);
  child:=nheapmax;
  while child div 2 > 0 do
    begin
      parent:=child div 2;
      if d[heapmax[parent]].p > d[sl].p then break;
      heapmax[child]:=heapmax[parent];
      d[heapmax[child]].pos2:=child;
      child:=parent;
    end;
  heapmax[child]:=sl;
  d[sl].pos2:=child;
  inc(nheapmin);
  child:=nheapmin;
  while child div 2 > 0 do
    begin
      parent:= child div 2;
      if d[heapmin[parent]].p < d[sl].p then break;
      heapmin[child]:=heapmin[parent];
      d[heapmin[child]].pos1:=child;
      child:=parent;
    end;
  heapmin[child]:=sl;
  d[sl].pos1:=child;
end;
 
procedure solve2;
var
  num, r, c, v: longint;
begin
  num:=heapmax[1];
  writeln(f1,d[num].gt);
  r:=1;
  v:=heapmax[nheapmax];
  dec(nheapmax);
  while r*2 <= nheapmax do
    begin
      c:=r*2;
      if (c < nheapmax) and (d[heapmax[c+1]].p > d[heapmax[c]].p) then inc(c);
      if d[heapmax[c]].p <= d[v].p then break;
      heapmax[r]:=heapmax[c];
      d[heapmax[r]].pos2:=r;
      r:=c;
    end;
  heapmax[r]:=v;
  d[v].pos2:=r;
  r:=d[num].pos1;
  if r = nheapmin then dec(nheapmin)
  else
    begin
      v:=heapmin[nheapmin];
      dec(nheapmin);
      while r div 2 > 0 do
        begin
          c:=r div 2;
          if d[heapmin[c]].p < d[v].p then break;
          heapmin[r]:=heapmin[c];
          d[heapmin[r]].pos1:=r;
          r:=c;
        end;
      heapmin[r]:=v;
      d[v].pos1:=r;
    end;
end;
 
procedure solve3;
var
  num, r, v, c: longint;
begin
  num:=heapmin[1];
  writeln(f1,d[num].gt);
  r:=1;
  v:=heapmin[nheapmin];
  dec(nheapmin);
  while r * 2 <=nheapmin do
    begin
      c:=r*2;
      if (c < nheapmin) and (d[heapmin[c+1]].p < d[heapmin[c]].p) then inc(c);
      if d[heapmin[c]].p >= d[v].p then break;
      heapmin[r]:=heapmin[c];
      d[heapmin[r]].pos1:=r;
      r:=c;
    end;
  heapmin[r]:=v;
  d[v].pos1:=r;
  r:=d[num].pos2;
  if r = nheapmax then dec(nheapmax)
  else
    begin
      v:=heapmax[nheapmax];
      dec(nheapmax);
      while r div 2 > 0 do
        begin
          c:= r div 2;
          if d[heapmax[c]].p > d[v].p then break;
          heapmax[r]:=heapmax[c];
          d[heapmax[r]].pos2:=r;
          r:=c;
        end;
      heapmax[r]:=v;
      d[v].pos2:=r;
    end;
end;
 
procedure solve;
var
  num, k, p1: longint;
 
begin
  sl:=0;
 
  while not seekeof(f) do
    begin
      read(f, num);
      if num = 1 then
        begin
          inc(sl);
          read(f, k, p1);
          d[sl].gt:=k;
          d[sl].p:=p1;
          push(sl);
 
        end;
      if num = 2 then solve2;
      if num = 3 then solve3;
    end;
 
end;
 
 
begin
  open;
  solve;
  closefile;
end.