- Sử dụng 1 heapmin và 1 heapmax.
- Với yêu cầu 1: thực hiện updatemin và updatemax (cập nhập lại heapmin và heapmax).
- Với yêu cầu 2: 
  + Mình gán xr:=popmax; (thằng có độ ưu tiên cao nhất).
  + Xuất nó ra.
  + Gán lại độ ưu tiên d[xr]:=+oo;
  + Updatemin(xr); (cập nhập lại vị trí của nó trong heapmin, nghĩa là bây giờ xr là phần tử có độ ưu tiên lớn nhất trong heapmin).
  + Giảm số lượng phần tử của heapmin đi 1 (loại xr ra khỏi heapmin).
  + Gán posmin[xr]:=0; (xr không còn xuất hiện trong heapmin nữa).
- Với yêu cầu 3: mình làm tương tự yêu cầu 2.

- ntemax, ntemin là số lượng phần tử của heapmax,heapmin

 
PROGRAM Double_Heap;
Const   MaxN=1000*1000;
        oo=1000*1000*1000;
Var     heapmax,heapmin,posmax,posmin,d:array[0..maxn+1] of longint;
        ntemax,ntemin:longint;
 
Procedure updatemin(i:longint);
Var     cha,con:longint;
Begin
        con:=posmin[i];
        if con=0 then
        begin
                inc(ntemin);
                con:=ntemin;
        end;
        Repeat
                cha:=con div 2;
                if (cha=0) or (d[heapmin[cha]]<=d[i]) then break;
                heapmin[con]:=heapmin[cha];
                posmin[heapmin[con]]:=con;
                con:=cha;
        Until false;
        heapmin[con]:=i;
        posmin[i]:=con;
End;
 
Function popmin:longint;
Var     cha,con,i:longint;
Begin
        popmin:=heapmin[1];
        posmin[heapmin[1]]:=0;
        i:=heapmin[ntemin];
        dec(ntemin);
        cha:=1;
        Repeat
                con:=cha*2;
                if (con<ntemin) and (d[heapmin[con+1]]<d[heapmin[con]]) then inc(con);
                if (con>ntemin) or (d[heapmin[con]]>=d[i]) then break;
                heapmin[cha]:=heapmin[con];
                posmin[heapmin[cha]]:=cha;
                cha:=con;
        Until false;
        heapmin[cha]:=i;
        posmin[i]:=cha;
End;
 
Procedure updatemax(i:longint);
Var     cha,con:longint;
Begin
        con:=posmax[i];
        if con=0 then
        begin
                inc(ntemax);
                con:=ntemax;
        end;
        Repeat
                cha:=con div 2;
                if (cha=0) or (d[heapmax[cha]]>=d[i]) then break;
                heapmax[con]:=heapmax[cha];
                posmax[heapmax[con]]:=con;
                con:=cha;
        Until false;
        heapmax[con]:=i;
        posmax[i]:=con;
End;
 
Function popmax:longint;
Var     cha,con,i:longint;
Begin
        popmax:=heapmax[1];
        posmax[heapmax[1]]:=0;
        i:=heapmax[ntemax];
        dec(ntemax);
        cha:=1;
        Repeat
                con:=cha*2;
                if (con<ntemax) and (d[heapmax[con+1]]>d[heapmax[con]]) then inc(con);
                if (con>ntemax) or (d[heapmax[con]]<=d[i]) then break;
                heapmax[cha]:=heapmax[con];
                posmax[heapmax[cha]]:=cha;
                cha:=con;
        Until false;
        heapmax[cha]:=i;
        posmax[i]:=cha;
End;
 
Procedure khoitao;
Var     i:longint;
Begin
        For i:=1 to maxn do
        begin
                posmax[i]:=0;
                posmin[i]:=0;
        end;
End;
 
Procedure giai;
Var     yc,i,xr,vt:longint;
Begin
        Repeat
                read(yc);
                if yc=0 then break
                else
                if yc=1 then
                begin
                        readln(i,d[i]);
                        updatemin(i);
                        updatemax(i);
                end
                else
                if yc=2 then
                begin
                        readln;
                        if ntemax=0 then writeln(0)
                        else begin
                                xr:=popmax;
                                writeln(xr);
                                //xuly
                                d[xr]:=oo;
                                updatemin(xr);
                                dec(ntemin);
                                posmin[xr]:=0;
                        end;
                end
                else
                if yc=3 then
                begin
                        readln;
                        if ntemin=0 then writeln(0)
                        else begin
                                xr:=popmin;
                                writeln(xr);
                                //xuly
                                d[xr]:=-oo;
                                updatemax(xr);
                                dec(ntemax);
                                posmax[xr]:=0;
                        end;
                end;
 
        Until yc=0;
End;
 
BEGIN
        khoitao;
        giai;
END.

 
const maxN=1000000;
var topmin,topmax:longint;
        p,cs,hmin,hmax:array[1..maxN] of longint;
        c:array[1..maxN] of boolean;
{===================================}
procedure upmin(x:longint); inline;
var i,j:longint;
begin
        i:=topmin;
        j:=i shr 1;
        while (j>0) and (p[hmin[j]]>p[x]) do
        begin
                hmin[i]:=hmin[j];
                i:=j;
                j:=i shr 1;
        end;
        hmin[i]:=x;
end;
{===================================}
procedure upmax(x:longint); inline;
var i,j:longint;
begin
        i:=topmax;
        j:=i shr 1;
        while (j>0) and (p[hmax[j]]<p[x]) do
        begin
                hmax[i]:=hmax[j];
                i:=j;
                j:=i shr 1;
        end;
        hmax[i]:=x;
end;
{===================================}
procedure push(x:longint); inline;
begin
        c[x]:=false;
        inc(topmin);
        inc(topmax);
        upmin(x);
        upmax(x);
end;
{===================================}
procedure downmin; inline;
var i,j,x:longint;
begin
        x:=hmin[topmin];
        dec(topmin);
        i:=1;
        j:=i shl 1;
        while j<=topmin do
        begin
                if (j<topmin) and (p[hmin[j]]>p[hmin[j+1]]) then inc(j);
                if p[hmin[j]]>=p[x] then break;
                hmin[i]:=hmin[j];
                i:=j;
                j:=i shl 1;
        end;
        hmin[i]:=x;
end;
{===================================}
procedure downmax; inline;
var i,j,x:longint;
begin
        x:=hmax[topmax];
        dec(topmax);
        i:=1;
        j:=i shl 1;
        while j<=topmax do
        begin
                if (j<topmax) and (p[hmax[j]]<p[hmax[j+1]]) then inc(j);
                if p[hmax[j]]<=p[x] then break;
                hmax[i]:=hmax[j];
                i:=j;
                j:=i shl 1;
        end;
        hmax[i]:=x;
end;
{===================================}
procedure getmin; inline;
var s:longint;
begin
        s:=0;
        while (topmin>0) and (c[hmin[1]]) do downmin;
        if topmin>0 then
        begin
                s:=cs[hmin[1]];
                c[hmin[1]]:=true;
                downmin;
        end;
        writeln(s);
end;
{===================================}
procedure getmax; inline;
var s:longint;
begin
        s:=0;
        while (topmax>0) and (c[hmax[1]]) do downmax;
        if topmax>0 then
        begin
                s:=cs[hmax[1]];
                c[hmax[1]]:=true;
                downmax;
        end;
        writeln(s);
end;
{===================================}
procedure enter; inline;
var r,i:longint;
begin
        topmin:=0;
        topmax:=0;
        i:=0;
        while not eof do
        begin
                read(r);
                if r=0 then exit;
                if r=1 then
                begin
                        inc(i);
                        read(cs[i],p[i]);
                        push(i);
                end;
                if r=2 then getmax;
                if r=3 then getmin;
        end;
end;
{====================================}
begin
        enter;
end.