Ngân hàng BIG-Bank mở một chi nhánh ở Bucharest và được trang bị một máy tính hiện đại với các công nghệ mới nhập, C2#, VC3 ~+~ ...chỉ chuối mỗi cái là không ai biết lập trình.

Họ cần một phần mềm mô tả hoạt động của ngân hàng như sau: mỗi khách hàng có một mã số là số nguyên ~K~, và khi đến ngân hàng giao dịch, họ sẽ nhận được ~1~ số ~P~ là thứ tự ưu tiên của họ. Các thao tác chính như sau

• ~0~ Kết thúc phục vụ
• ~1~ ~K~ ~P~ Thêm khách hàng ~K~ vào hàng đợi với độ ưu tiên ~P~
• ~2~ Phục vụ người có độ ưu tiên cao nhất và xóa khỏi danh sách hàng đợi
• ~3~ Phục vụ người có độ ưu tiên thấp nhất và xóa khỏi danh sách hàng đợi.
• Tất nhiên là họ cần bạn giúp rồi.

Input

Mỗi dòng của input là ~1~ yêu cầu, và chỉ yêu cầu cuối cùng mới có giá trị là ~0~. Giả thiết là khi có yêu cầu ~1~ thì không có khách hàng nào khác có độ ưu tiên là ~P~.

Output

Với mỗi yêu cầu ~2~ hoặc ~3~, in ra trên ~1~ dòng mã số của khách hàng được phục vụ tương ứng. Nếu có yêu cầu mà hàng đợi rỗng, in ra số ~0~.

Giới hạn

~K \le 10^{6}~, và ~P \le 10^{7}~.

Một khách hàng có thể yêu cầu phục vụ nhiều lần và với các độ ưu tiên khác nhau.

Sample Input

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

Sample Output

0
20
30
10
0