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.

Dữ liệu vào

• 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\).

Dữ liệu ra

• 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\)
• \(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.

Input 1

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

Output 1

0
20
30
10
0