某个银行很傲娇，来了一些客户，有时先接待优先级最高的客户，有时先接待优先级最低的客户，有如下四种操作：

$0$：系统停止服务。

$1$ $K$ $P$：增加一个 $ID$ 为 $K(K≤10^6)$*的客户，其优先级是 $P(P≤107)4。

$2$：查询优先级最高的客户，接待他，并从等候队列里删除。

$3$：查询优先级最低的客户，接待他，并从等候队列里删除。

你的任务是依次输出这些客户的 $ID$。

输入格式

若干行，以 $0$ 结束（总操作数不超过 $10^5$）。

一个客户可能访问多次；保证在任意时刻，队列中的优先级各不相同。

输出格式

对于 2和 3 操作，一行一个整数表示 ID，若查询无结果，则输出 0。

格式说明输出时每行末尾的多余空格，不影响答案正确性

输入、输出要求要求使用「文件输入、输出」的方式解题，输入文件为 bank.in，输出文件为 bank.out

样例输入

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

样例输出

0
20
30
10
0