Bàn điều phối ưu tiên

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

Một cụm máy chủ nhận các tác vụ xử lý từ nhiều dịch vụ. Mỗi tác vụ có một id duy nhất và một mức priority. Khi tài nguyên rảnh, bộ điều phối phải chọn tác vụ quan trọng nhất; đồng thời màn hình giám sát đôi lúc chỉ cần xem tác vụ đang đứng đầu mà chưa chạy nó.

Hệ thống hỗ trợ ba loại lệnh:

• ADD id priority: thêm một tác vụ mới. Các id trong lệnh ADD được đảm bảo không lặp.
• TOP: in id của tác vụ đang chờ có priority lớn nhất nhưng không xóa tác vụ.
• RUN: in id của tác vụ có priority lớn nhất rồi xóa tác vụ đó khỏi hàng chờ.

Nếu nhiều tác vụ có cùng priority, tác vụ có id nhỏ hơn được ưu tiên. Nếu TOP hoặc RUN khi hàng chờ rỗng, in EMPTY.

Yêu cầu

Xử lý toàn bộ chuỗi lệnh và in đúng phản hồi của hệ thống.

Input

• Dòng 1: số lệnh q.
• q dòng tiếp theo là các lệnh.

Output

In một dòng cho mỗi lệnh TOP hoặc RUN.

Ràng buộc

• 1 <= q <= 2 * 10^5
• 1 <= id, priority <= 10^9
• Mỗi id chỉ xuất hiện trong tối đa một lệnh ADD.

Chấm điểm

Ví dụ 1

Input

7
ADD 10 5
ADD 3 5
TOP
RUN
TOP
RUN
RUN

Output

3
3
10
10
EMPTY

Giải thích. Hai tác vụ có cùng priority 5; quy tắc hòa ưu tiên id nhỏ hơn nên tác vụ 3 đứng đầu. TOP chỉ xem, còn RUN mới xóa tác vụ khỏi hàng chờ.

Ví dụ 2

Input

4
TOP
ADD 7 100
RUN
TOP

Output

EMPTY
7
EMPTY

Giải thích. Lần TOP đầu tiên gặp hàng chờ rỗng. Sau khi thêm tác vụ 7, lệnh RUN chạy và xóa nó, vì vậy TOP cuối cùng lại nhận EMPTY.

Thông tin bài tập

Nguồn: FULLHOUSE DEV — Self-generated.