Bảng ưu tiên cập nhật lười

Bối cảnh và bài toán

Một hệ thống giữ nhiều task theo id, mỗi task hiện tại có một priority. Lệnh SET id p tạo hoặc cập nhật priority; REMOVE id xóa task nếu tồn tại; TOP cần trả task priority lớn nhất, nếu hòa chọn ID nhỏ nhất. Hệ thống không có thao tác sửa/xóa phần tử tùy ý trực tiếp trong heap.

Yêu cầu

Xử lý toàn bộ lệnh và trả lời TOP.

Input

• Dòng 1: q.
• q dòng, mỗi dòng là SET id p, REMOVE id, hoặc TOP.

Output

Với mỗi TOP, in id priority của task tốt nhất hoặc EMPTY.

Ràng buộc

• 1 <= q <= 2 * 10^5
• 1 <= id, p <= 10^9

Chấm điểm

Ví dụ 1

Input

7
SET 10 5
SET 20 7
TOP
SET 10 9
TOP
REMOVE 10
TOP

Output

20 7
10 9
20 7

Giải thích. Entry cũ (10,5) vẫn có thể còn trong heap nhưng không còn hợp lệ sau SET.

Ví dụ 2

Input

3
TOP
SET 1 3
TOP

Output

EMPTY
1 3

Giải thích. TOP đầu tiên khi chưa có task.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.