Bài 32.2. Biên niên sử Khoa học Viễn tưởng - [Độ khó: Khá]

Một nhà sử học về khoa học viễn tưởng muốn sắp xếp và quản lý các sự kiện lớn theo trình tự thời gian. Tuy nhiên, các khám phá mới hoặc thông tin bổ sung thường xuyên xuất hiện, đòi hỏi phải chèn các sự kiện vào giữa chuỗi đã có, hoặc điều chỉnh/xóa bỏ các sự kiện sai sót. Để dễ dàng điều hướng qua dòng thời gian (tiến và lùi), ông quyết định sử dụng một Danh sách liên kết đôi (Doubly Linked List).

Bạn cần phát triển một chương trình giúp nhà sử học quản lý "biên niên sử" này. Mỗi sự kiện có một mã ID duy nhất và một mô tả ngắn gọn (không cần xử lý mô tả, chỉ cần ID).

INPUT FORMAT

Dòng đầu tiên là một số nguyên N (1 <= N <= 1000), số lượng thao tác. Tiếp theo là N dòng, mỗi dòng mô tả một thao tác:

• INSERT_AFTER <event_ID> <ref_ID>: Chèn một sự kiện mới event_ID vào sau sự kiện có ref_ID. Nếu ref_ID là -1, sự kiện mới được chèn vào cuối danh sách. event_ID và ref_ID là các số nguyên dương duy nhất.
• INSERT_BEFORE <event_ID> <ref_ID>: Chèn một sự kiện mới event_ID vào trước sự kiện có ref_ID. Nếu ref_ID là -1, sự kiện mới được chèn vào đầu danh sách.
• DELETE <event_ID>: Xóa sự kiện có event_ID khỏi biên niên sử.
• PRINT_FORWARD: In ra các event_ID theo trình tự thời gian (từ đầu đến cuối).
• PRINT_BACKWARD: In ra các event_ID ngược trình tự thời gian (từ cuối về đầu). Tất cả các event_ID đều là số nguyên dương và không trùng lặp (1 <= event_ID <= 10^9). Các thao tác INSERT_AFTER và INSERT_BEFORE đảm bảo ref_ID luôn tồn tại trong danh sách trừ trường hợp ref_ID là -1. Các thao tác DELETE đảm bảo event_ID luôn tồn tại trong danh sách.

OUTPUT FORMAT

Với mỗi thao tác PRINT_FORWARD hoặc PRINT_BACKWARD, in ra các event_ID cách nhau bởi dấu cách. Nếu danh sách rỗng, in ra "Empty".

Ví dụ:

Input:

8
INSERT_AFTER 10 -1
INSERT_BEFORE 20 10
INSERT_AFTER 30 20
PRINT_FORWARD
DELETE 20
INSERT_AFTER 40 30
PRINT_BACKWARD
DELETE 10

Output:

20 30 10
40 30

Giải thích:

• INSERT_AFTER 10 -1: Chèn 10 vào cuối. List: 10.
• INSERT_BEFORE 20 10: Chèn 20 trước 10. List: 20 <-> 10.
• INSERT_AFTER 30 20: Chèn 30 sau 20. List: 20 <-> 30 <-> 10.
• PRINT_FORWARD: In ra 20 30 10.
• DELETE 20: Xóa 20. List: 30 <-> 10.
• INSERT_AFTER 40 30: Chèn 40 sau 30. List: 30 <-> 40 <-> 10.
• PRINT_BACKWARD: In ra 10 40 30.
• DELETE 10: Xóa 10. List: 30 <-> 40.