题目描述

新成立的巴尔干投资集团银行（大银行）在布加勒斯特开设了一个新办公室，配备了由 \(\text{IBM}\) 罗马尼亚提供的现代计算环境，并使用现代信息技术。

像往常一样，银行的每个客户都用一个正整数K来标识，当到达银行时，他或她收到一个正整数优先权 \(P\)。银行的年轻经理提议打破传统，有时服务优先权最高的，有时候服务优先权最低的。因此，系统将接收以下类型的请求：

\(1.\) 0 系统需要停止服务。

\(2.\) 1 K P 用优先级 \(P\) 将客户 \(K\) 添加到等待列表中（数据保证 \(K\) 和 \(P\) 无重）

\(3.\) 2 以最大优先级服务客户，并将其从等候名单中删除。

\(4.\) 3 以最小优先级服务客户，并将其从等候名单中删除。

您的任务是帮助银行的软件工程师编写一个程序来实现所请求的服务策略。

格式

输入格式

输入的每一行包含一个可能的请求；只有最后一行包含停止请求（代码 \(0\)）。

客户可以多次到达，每次可获得不同的优先权。但输入数据保证，同一时刻请求列表中不会有多个相同客户存在，或多个相同优先级。

输出格式

对于每个带有代码 \(2\) 或 \(3\) 的请求，程序必须在单独行中输出客户标识 \(K\)。如果请求在等待列表为空时到达，则程序输出零。

样例1

样例输入1

2
1 20 14
1 30 3
2
1 10 99
3
2
2
0

样例输出1

0
20
30
10
0

限制

时间：\(1s\) 空间：\(128M\)

对于 \(30\%\) 的数据：命令数 \(<=10^3; k<=10^3; p<=10^4\);

对于 \(100\%\) 的数据：命令数 \(<=10^5; k<=10^6; p<=10^7\)。

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)
模拟赛\(T3\)