Description

As the chief dispatcher, you are responsible for managing trains across multiple platforms. A train is essentially a sequence of train cars, each with a unique ID.

There are $M$ platforms in the station, numbered from $1$ to $M$. Initially, all platforms are empty. You will receive $Q$ operations, each belonging to one of the following five types:

• ENTER p c: A newly manufactured train car with a unique ID $c$ arrives at platform $p$. It is attached to the very end (tail) of the current train on that platform.
• MERGE p_src p_dest: The entire train on platform $p_{src}$ is moved and attached to the end of the train on platform $p_{dest}$. After this operation, platform $p_{src}$ becomes empty. If $p_{src}$ is empty before this operation, do nothing.
• REMOVE p c: Locate car $c$ currently on platform $p$ and remove it completely. The train is then reconnected, meaning the car immediately in front of $c$ (if any) and the car immediately behind $c$ (if any) are directly linked together.
• REVERSE p: Reverse the order of all cars of the train on platform $p$.
• CHECK p c k: Starting from car $c$ on platform $p$, move $k$ cars towards the front of the train. Output the ID of the car you reach. If you reach the very first car of the train before taking $k$ steps, stop and output the ID of the first car.

Hint

During peak hours, thousands of cars need to be reassigned every minute.

To prevent severe system bottlenecks, your dispatching system must be highly optimized.

Think about how to find a specific car in $O(1)$ time to perform the REMOVE and CHECK operations efficiently.

Input

The first line contains two integers $M$ and $Q$, representing the total number of platforms and the number of operations.

The following $Q$ lines each contain a command in the format described above.

It is guaranteed that:

• For ENTER, the car ID $c$ has never appeared before.
• For MERGE and SPLIT, $p_{src}$ and $p_{dest}$ are different ($p_{src} \neq p_{dest}$).
• For REMOVE and CHECK, car $c$ is guaranteed to exist currently on platform $p$.

Constraints

• $1 \le M \le 100,000$
• $1 \le Q \le 200,000$
• $1 \le p, p_{src}, p_{dest} \le M$
• $1 \le c \le 1,000,000$
• $0 \le k \le 100,000$
• The sum of the lengths of the trains reversed across all REVERSE operations will not exceed $5 \times 10^5$.

Subtasks

• Testcase 1: only ENTER and MERGE
• Testcase 2: only ENTER and REMOVE
• Testcase 3: only ENTER and REVERSE
• Testcase 4: only ENTER and CHECK
• Testcases 5-8: All operations are possible.
• Testcases 1-6: $c \le 100$.
• Testcases 7-8: No additional constraints.

Output

1. For each CHECK operation, output the resulting car ID on a new line.
2. After processing all $Q$ operations, output the final sequence of train cars on each non-empty platform.
   • For each non-empty platform from $1$ to $M$, output a line starting with the platform number, followed by a colon : and a space, and then the IDs of the cars on that platform in order from front to end, separated by a single space.
   • If a platform is completely empty, do not output anything for that platform.

Note for Sample I/O

1. ENTER 1 10: Platform 1 has [10].
2. ENTER 1 20: Platform 1 has [10, 20].
3. ENTER 2 30: Platform 2 has [30].
4. MERGE 2 1: Platform 1 has [10, 20, 30], Platform 2 is empty. (Source=2, Dest=1)
5. CHECK 1 30 1: Start at 30, move 1 step towards the front -> reaches 20. Output 20.
6. CHECK 1 30 5: Start at 30, moving 5 steps to the front exceeds the train length, so it stops at the head. Output 10.
7. REVERSE 1: Platform 1 has [30, 20, 10].
8. CHECK 1 10 2: Start at 10, move 2 steps towards the front -> reaches 30. Output 30.
9. ENTER 3 40: Platform 3 has [40].
10. REMOVE 1 20: Car 20 is removed from Platform 1. Platform 1 becomes [30, 10].
11. MERGE 1 3: Platform 3 becomes [40, 30, 10], Platform 1 is empty. (Source=1, Dest=3)

Sample Input  Download

Sample Output  Download

Partial Judge Code

14945.c

Partial Judge Header

14945.h

Tags

Discuss