Bài 32.1. Quản lý Đội hình tuần tra - [Độ khó: Khá]

Trong một hệ thống an ninh hiện đại, các robot tuần tra được lập trình để di chuyển theo một lộ trình cố định và lặp lại liên tục. Mỗi robot trong đội hình có một mã ID duy nhất. Để tối ưu hóa hiệu quả, đôi khi cần thêm một robot mới vào đội hình sau một robot cụ thể nào đó, hoặc loại bỏ một robot khỏi đội hình nếu nó gặp sự cố. Toàn bộ đội hình tuần tra được tổ chức như một danh sách liên kết tròn để mô phỏng vòng lặp tuần tra không ngừng nghỉ.

Nhiệm vụ của bạn là xây dựng một hệ thống quản lý đội hình tuần tra sử dụng danh sách liên kết tròn. Hệ thống cần hỗ trợ các thao tác: thêm robot, loại bỏ robot, và in ra lộ trình tuần tra hiện tại.

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:

• ADD <robot_ID> <after_ID>: Thêm một robot mới có robot_ID vào đội hình sau robot có after_ID. Nếu after_ID là -1, robot mới được thêm vào đầu (nếu danh sách rỗng hoặc thêm vào sau robot cuối cùng nếu đã có robot). robot_ID và after_ID là các số nguyên dương duy nhất.
• REMOVE <robot_ID>: Loại bỏ robot có robot_ID khỏi đội hình.
• PRINT: In ra lộ trình tuần tra hiện tại. Tất cả các robot_ID đều là số nguyên dương và không trùng lặp (1 <= robot_ID <= 10^9). Các thao tác ADD đảm bảo after_ID luôn tồn tại trong danh sách trừ trường hợp after_ID là -1. Các thao tác REMOVE đảm bảo robot_ID luôn tồn tại trong danh sách.

OUTPUT FORMAT

Với mỗi thao tác PRINT, in ra các robot_ID theo thứ tự tuần tra, bắt đầu từ robot đầu tiên được thêm vào (hoặc robot được thêm vào đầu tiên nếu không có robot nào được thêm vào sau), cách nhau bởi dấu cách. Nếu danh sách rỗng, in ra "Empty".

Ví dụ:

Input:

6
ADD 1 -1
ADD 3 1
ADD 2 1
PRINT
REMOVE 3
PRINT

Output:

1 2 3
1 2

Giải thích:

• ADD 1 -1: Thêm robot ID 1 vào đội hình. Danh sách: 1 (và 1 trỏ về chính nó).
• ADD 3 1: Thêm robot ID 3 sau robot ID 1. Danh sách: 1 -> 3 -> 1 (chuỗi tuần tra: 1, 3).
• ADD 2 1: Thêm robot ID 2 sau robot ID 1. Lưu ý rằng 1 đã được theo sau bởi 3. Khi thêm 2 sau 1, 2 sẽ nằm giữa 1 và 3. Danh sách: 1 -> 2 -> 3 -> 1 (chuỗi tuần tra: 1, 2, 3).
• PRINT: In ra chuỗi tuần tra: 1 2 3.
• REMOVE 3: Loại bỏ robot ID 3. Danh sách: 1 -> 2 -> 1 (chuỗi tuần tra: 1, 2).
• PRINT: In ra chuỗi tuần tra: 1 2.