{$MODE OBJFPC}
{$DEFINE STDIO}
const
{$IFDEF FILEIO}
tfi='MSE07B.INP';
tfo='MSE07B.OUT';
{$ELSE}
tfi='';
tfo='';
{$ENDIF}
maxn=trunc(1e6);
var a:array[1..maxn] of longint;
ah,ih:array[1..maxn] of longint;
pi,pa:array[1..maxn] of longint;
nha,nhi:longint;
cmd,k:longint;
fi,fo:text;
Procedure opf;
Begin
assign(fi,tfi);
reset(fi);
assign(fo,tfo);
rewrite(fo);
End;
Procedure clf;
Begin
close(fi);
close(fo);
End;
Procedure swap(var a,b:longint);
var c:longint;
Begin
c:=a;
a:=b;
b:=c;
End;
Procedure inserta(i:longint);
var u,v:longint;
Begin
inc(nha);
ah[nha]:=i;
pa[i]:=nha;
u:=nha;
while (u<>1) do
Begin
v:=u div 2;
if a[ah[u]]>a[ah[v]] then
Begin
swap(ah[u],ah[v]);
pa[ah[u]]:=u;
pa[ah[v]]:=v;
u:=v;
End else break;
End;
End;
Procedure inserti(i:longint);
var u,v:longint;
Begin
inc(nhi);
ih[nhi]:=i;
pi[i]:=nhi;
u:=nhi;
while u<>1 do
Begin
v:=u div 2;
if a[ih[u]]<a[ih[v]] then
Begin
swap(ih[u],ih[v]);
pi[ih[u]]:=u;
pi[ih[v]]:=v;
u:=v;
End else break;
End;
End;
Procedure deletea(u:longint);
var v:longint;
Begin
ah[u]:=ah[nha];
ah[nha]:=0;
dec(nha);
while u<nha do
Begin
v:=2*u;
if v>nha then break;
if (v+1<=nha) and (a[ah[v]]<a[ah[v+1]]) then inc(v);
if a[ah[u]]<a[ah[v]] then
Begin
swap(ah[u],ah[v]);
pa[ah[u]]:=u;
pa[ah[v]]:=v;
u:=v;
End else break;
End;
End;
Procedure deletei(u:longint);
var v:longint;
Begin
ih[u]:=ih[nhi];
ih[nhi]:=0;
dec(nhi);
while u<nhi do
Begin
v:=u*2;
if v>nhi then break;
if (v+1<=nhi) and (a[ih[v]]>a[ih[v+1]]) then inc(v);
if a[ih[u]]>a[ih[v]] then
Begin
swap(ih[u],ih[v]);
pi[ih[u]]:=u;
pi[ih[v]]:=v;
u:=v;
End else break;
End;
End;
Procedure main;
Begin
nhi:=0;
nha:=0;
repeat
read(fi,cmd);
if cmd=1 then
Begin
read(fi,k,a[k]);
inserta(k);
inserti(k);
End;
if cmd=2 then
if nha=0 then writeln(fo,0) else
Begin
writeln(fo,ah[1]);
deletei(pi[ah[1]]);
deletea(1);
End;
if cmd=3 then
if nhi=0 then writeln(fo,0) else
Begin
writeln(fo,ih[1]);
deletea(pa[ih[1]]);
deletei(1);
End;
until cmd=0;
End;
Begin
opf;
main;
clf;
End.
eyRNT0RFIE9CSkZQQ30KeyRERUZJTkUgU1RESU99Cgpjb25zdAp7JElGREVGIEZJTEVJT30KCQkJCXRmaT0nTVNFMDdCLklOUCc7CiAgICAgICAgdGZvPSdNU0UwN0IuT1VUJzsKeyRFTFNFfQoJCQkJdGZpPScnOwogICAgICAgIHRmbz0nJzsKeyRFTkRJRn0KCgkJCQltYXhuPXRydW5jKDFlNik7CgoKdmFyIGE6YXJyYXlbMS4ubWF4bl0gb2YgbG9uZ2ludDsKCgkJYWgsaWg6YXJyYXlbMS4ubWF4bl0gb2YgbG9uZ2ludDsKICAgIHBpLHBhOmFycmF5WzEuLm1heG5dIG9mIGxvbmdpbnQ7CiAgICBuaGEsbmhpOmxvbmdpbnQ7CgogICAgY21kLGs6bG9uZ2ludDsKCgkJZmksZm86dGV4dDsKClByb2NlZHVyZSBvcGY7CglCZWdpbgogICAgCWFzc2lnbihmaSx0ZmkpOwogICAgICByZXNldChmaSk7CgogICAgICBhc3NpZ24oZm8sdGZvKTsKICAgICAgcmV3cml0ZShmbyk7CiAgRW5kOwoKUHJvY2VkdXJlIGNsZjsKCUJlZ2luCiAgCWNsb3NlKGZpKTsKICAgIGNsb3NlKGZvKTsKICBFbmQ7CgpQcm9jZWR1cmUgc3dhcCh2YXIgYSxiOmxvbmdpbnQpOwoJdmFyIGM6bG9uZ2ludDsKICBCZWdpbgogICAgYzo9YTsKICAgIGE6PWI7CiAgICBiOj1jOwogIEVuZDsKClByb2NlZHVyZSBpbnNlcnRhKGk6bG9uZ2ludCk7Cgl2YXIgdSx2OmxvbmdpbnQ7CglCZWdpbgogICAgaW5jKG5oYSk7CiAgICBhaFtuaGFdOj1pOwogICAgcGFbaV06PW5oYTsKCiAgICB1Oj1uaGE7CiAgICB3aGlsZSAodTw+MSkgZG8KCQlCZWdpbgogIAkJdjo9dSBkaXYgMjsKICAgICAgaWYgYVthaFt1XV0+YVthaFt2XV0gdGhlbgogICAgICBCZWdpbgogICAgICAJc3dhcChhaFt1XSxhaFt2XSk7CiAgICAgICAgcGFbYWhbdV1dOj11OwogICAgICAgIHBhW2FoW3ZdXTo9djsKCiAgICAgICAgdTo9djsKICAgICAgRW5kIGVsc2UgYnJlYWs7CgogICAgRW5kOwogIEVuZDsKClByb2NlZHVyZSBpbnNlcnRpKGk6bG9uZ2ludCk7Cgl2YXIgdSx2OmxvbmdpbnQ7CiAgQmVnaW4KICAJaW5jKG5oaSk7CiAgICBpaFtuaGldOj1pOwogICAgcGlbaV06PW5oaTsKCiAgICB1Oj1uaGk7CiAgICB3aGlsZSB1PD4xIGRvCiAgICBCZWdpbgogICAgCXY6PXUgZGl2IDI7CiAgICAgIGlmIGFbaWhbdV1dPGFbaWhbdl1dIHRoZW4KICAgICAgQmVnaW4KICAgICAgCXN3YXAoaWhbdV0saWhbdl0pOwogICAgICAgIHBpW2loW3VdXTo9dTsKCQkJCXBpW2loW3ZdXTo9djsKCiAgICAgICAgdTo9djsKICAgICAgRW5kIGVsc2UgYnJlYWs7CgogICAgRW5kOwogIEVuZDsKClByb2NlZHVyZSBkZWxldGVhKHU6bG9uZ2ludCk7Cgl2YXIgdjpsb25naW50OwoJQmVnaW4KCQlhaFt1XTo9YWhbbmhhXTsKICAgIGFoW25oYV06PTA7CiAgICBkZWMobmhhKTsKCiAgICB3aGlsZSB1PG5oYSBkbwogICAgQmVnaW4KICAgICAgdjo9Mip1OwogICAgICBpZiB2Pm5oYSB0aGVuIGJyZWFrOwogICAgICBpZiAodisxPD1uaGEpIGFuZCAoYVthaFt2XV08YVthaFt2KzFdXSkgdGhlbiBpbmModik7CgogICAgICBpZiBhW2FoW3VdXTxhW2FoW3ZdXSB0aGVuCiAgICAgIEJlZ2luCiAgICAgIAlzd2FwKGFoW3VdLGFoW3ZdKTsKICAgICAgICBwYVthaFt1XV06PXU7CiAgICAgICAgcGFbYWhbdl1dOj12OwoKICAgICAgICB1Oj12OwogICAgICBFbmQgZWxzZSBicmVhazsKCiAgICBFbmQ7CiAgRW5kOwoKUHJvY2VkdXJlIGRlbGV0ZWkodTpsb25naW50KTsKCXZhciB2OmxvbmdpbnQ7CiAgQmVnaW4KICAJaWhbdV06PWloW25oaV07CiAgICBpaFtuaGldOj0wOwogICAgZGVjKG5oaSk7CgogICAgd2hpbGUgdTxuaGkgZG8KICAgIEJlZ2luCiAgICAJdjo9dSoyOwogICAgICBpZiB2Pm5oaSB0aGVuIGJyZWFrOwogICAgICBpZiAodisxPD1uaGkpIGFuZCAoYVtpaFt2XV0+YVtpaFt2KzFdXSkgdGhlbiBpbmModik7CgogICAgICBpZiBhW2loW3VdXT5hW2loW3ZdXSB0aGVuCiAgICAgIEJlZ2luCiAgICAgIAlzd2FwKGloW3VdLGloW3ZdKTsKICAgICAgICBwaVtpaFt1XV06PXU7CiAgICAgICAgcGlbaWhbdl1dOj12OwoKICAgICAgICB1Oj12OwogICAgICBFbmQgZWxzZSBicmVhazsKCiAgICBFbmQ7CiAgRW5kOwoKUHJvY2VkdXJlIG1haW47CiAgQmVnaW4KICAgIG5oaTo9MDsKICAgIG5oYTo9MDsKICAJcmVwZWF0CiAgICAJcmVhZChmaSxjbWQpOwoKICAgICAgaWYgY21kPTEgdGhlbgogICAgICBCZWdpbgogICAgICAJcmVhZChmaSxrLGFba10pOwogICAgICAgIGluc2VydGEoayk7CiAgICAgICAgaW5zZXJ0aShrKTsKICAgICAgRW5kOwoKICAgICAgaWYgY21kPTIgdGhlbgogICAgICAgIGlmIG5oYT0wIHRoZW4gd3JpdGVsbihmbywwKSBlbHNlCiAgICAgICAgQmVnaW4KICAgICAgCSAJd3JpdGVsbihmbyxhaFsxXSk7CiAgICAgICAgIAlkZWxldGVpKHBpW2FoWzFdXSk7CiAgICAgICAgIAlkZWxldGVhKDEpOwogICAgICAgIEVuZDsKCiAgICAgIGlmIGNtZD0zIHRoZW4KICAgICAgICBpZiBuaGk9MCB0aGVuIHdyaXRlbG4oZm8sMCkgZWxzZQogICAgICAgIEJlZ2luCiAgICAgICAgICB3cml0ZWxuKGZvLGloWzFdKTsKICAgICAgICAgIGRlbGV0ZWEocGFbaWhbMV1dKTsKICAgICAgICAgIGRlbGV0ZWkoMSk7CiAgICAgICAgRW5kOwogICAgdW50aWwgY21kPTA7CiAgRW5kOwoKQmVnaW4KCW9wZjsKICBtYWluOwogIGNsZjsKRW5kLgo=