Bảo đang thiết kế một kho hàng tự động thông minh. Các kiện hàng trong kho được gán nhãn bằng các mã số định danh nguyên dương. Để việc bốc xếp hàng diễn ra tối ưu, robot bốc xếp cần thực hiện các thao tác:

• 1 X: Nhập thêm một kiện hàng mới có mã số \(X\) vào kho.
• 2 X: Xuất một kiện hàng có mã số \(X\) ra khỏi kho (nếu có nhiều kiện hàng cùng mã \(X\), chỉ xuất đúng một kiện; nếu không có, bỏ qua yêu cầu).
• 3: Truy vấn mã số của kiện hàng nhỏ nhất hiện đang có trong kho.
• 4: Truy vấn mã số của kiện hàng lớn nhất hiện đang có trong kho.

Hãy giúp Bảo lập trình hệ thống quản lý kho hàng này.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên dương đại diện cho mã số của các kiện hàng ban đầu (\(1 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một yêu cầu thuộc một trong bốn loại trên. Với loại 1 và 2, dòng chứa thêm số nguyên dương \(X\) (\(1 \le X \le 10^9\)).

Định dạng đầu ra

• Với mỗi yêu cầu loại 3 và loại 4, in ra đáp án tương ứng trên một dòng. Nếu kho hàng đang trống, in ra -1.

Ràng buộc & Subtasks

• Subtask 1 (40% số điểm): \(N, Q \le 1000\).
• Subtask 2 (60% số điểm): \(N, Q \le 10^5\), các ràng buộc gốc.

Ví dụ

Input:

5 6
10 30 20 10 40
3
4
2 10
3
2 40
4

Output:

10
40
10
30

Giải thích:

• Các kiện hàng ban đầu: \(\{10, 10, 20, 30, 40\}\).
• Kiện hàng nhỏ nhất \(\to\) 10.
• Kiện hàng lớn nhất \(\to\) 40.
• Xuất 1 kiện 10 \(\to\) còn \(\{10, 20, 30, 40\}\).
• Kiện hàng nhỏ nhất \(\to\) 10.
• Xuất 1 kiện 40 \(\to\) còn \(\{10, 20, 30\}\).
• Kiện hàng lớn nhất \(\to\) 30.