Background

Special for beginners, ^_^

Description

银行的每个客户都有一个正整数标识$K$，到银行请求服务时将收到一个正整数优先级$P$。 银行经理提议打破传统，有时为优先级最低的客户服务，而不是为优先级最高的客户服务。系统将收到以下类型的请求： 0:系统需要停止服务。 1 K P：将客户$K$及其优先级$P$添加到等待队列中。 2：为优先级最高的客户提供服务，并将其从等待名单中删除。 3：为优先级最低的客户提供服务，并将其从等待名单中删除。

Format

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