Tèo đang xây dựng hệ thống giám sát hành trình cho đội tàu đánh cá trên biển. Mỗi tàu đánh cá phát ra một tín hiệu số đại diện cho tọa độ kinh độ hiện tại (dạng số nguyên). Hệ thống của Tèo cần liên tục cập nhật và thực hiện các yêu cầu truy vấn láng giềng để đảm bảo khoảng cách an toàn giữa các tàu:

• 1 X: Đăng ký thêm một tàu mới tại tọa độ \(X\). Nhiều tàu có thể ở cùng một tọa độ.
• 2 X: Loại bỏ một tàu tại tọa độ \(X\) khỏi hệ thống (nếu có nhiều tàu cùng ở tọa độ \(X\), chỉ loại bỏ đúng một tàu; nếu không có tàu nào, bỏ qua yêu cầu).
• 3 X: Tìm tọa độ lớn nhất của một tàu khác có tọa độ nghiêm ngặt nhỏ hơn \(X\) (predecessor). Nếu không tìm thấy, in ra -1.
• 4 X: Tìm tọa độ nhỏ nhất của một tàu khác có tọa độ nghiêm ngặt lớn hơn \(X\) (successor). Nếu không tìm thấy, in ra -1.

Hãy giúp Tèo lập trình bộ xử lý tọa độ an toàn 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 đại diện cho tọa độ ban đầu của các tàu (\(-10^9 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên type và \(X\) (\(type \in \{1, 2, 3, 4\}\), \(-10^9 \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 kết quả tương ứng trên một dòng riêng biệt.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000\).
• Subtask 2 (30% số điểm): Các tọa độ ban đầu và trong truy vấn đều dương (\(X > 0\)).
• Subtask 3 (40% số điểm): \(N, Q \le 10^5\), các ràng buộc gốc.

Ví dụ

Input:

5 6
10 20 15 10 30
3 15
4 15
1 12
3 15
2 10
3 11

Output:

10
20
12
10

Giải thích:

• Tọa độ ban đầu: \(\{10, 10, 15, 20, 30\}\).
• Yêu cầu 1 (3 15): Tọa độ lớn nhất \(< 15\) \(\to\) 10.
• Yêu cầu 2 (4 15): Tọa độ nhỏ nhất \(> 15\) \(\to\) 20.
• Yêu cầu 3 (1 12): Thêm tàu tại 12, danh sách tọa độ: \(\{10, 10, 12, 15, 20, 30\}\).
• Yêu cầu 4 (3 15): Tọa độ lớn nhất \(< 15\) \(\to\) 12.
• Yêu cầu 5 (2 10): Xóa một tàu tại 10, danh sách tọa độ: \(\{10, 12, 15, 20, 30\}\).
• Yêu cầu 6 (3 11): Tọa độ lớn nhất \(< 11\) \(\to\) 10.