Description

银行的每个客户都有一个正整数标识$K$，到银行请求服务时将收到一个正整数的优先级 $P$ 。银行经理提议打破传统，在某些时候调用优先级最低的客户，而不是优先级最高的客户。系统将收到以下类型的请求：

①$0$，系统需要停止服务；

②$1$ $K$ $P$，将客户$K$ 及优先级 $P$ 添加到等待列表中；

③$2$，为优先级最高的客户提供服务，并将其从等待名单中删除；

④$3$，为优先级最低的客户提供服务，并将其从等待名单中删除。

Input

输入的每一行都包含一个请求，只有最后一行包含停止请求（代码$0$）。假设有请求在列表中包含新客户（代码$1$），在同一客户的列表中没有其他请求或有相同的优先级，标识符$K$ 总是小于$10^6$ ，优先级$P$ 总是小于$10^7$ 。一个客户可以多次到银行请求服务，但是每次都获得不同的优先级。

Output

对代码为$2$或$3$的每个请求都单行输出所服务客户的标识。若请求在等待列表为空时到达，则输出$0$。

Samples

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

0
20
30
10
0

来源

POJ3481