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.SPLIT p_src c p_dest: Locate car $c$ which is currently somewhere on platform $p_{src}$. The train is decoupled just before car $c$. Car $c$ and all cars that were behind it are moved to the empty platform $p_{dest}$. The cars in front of $c$ remain on platform $p_{src}$.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.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 SPLIT and CHECK operations efficiently.
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:
ENTER, the car ID $c$ has never appeared before.MERGE and SPLIT, $p_{src}$ and $p_{dest}$ are different ($p_{src} \neq p_{dest}$).SPLIT and CHECK, car $c$ is guaranteed to exist on platform $p$ (or $p_{src}$).SPLIT, platform $p_{dest}$ is guaranteed to be empty before the operation.REVERSE operations will not exceed $5 \times 10^5$.ENTER and MERGEENTER and SPLITENTER and REVERSEENTER and CHECKCHECK operation, output the resulting car ID on a new line.: and a space, and then the IDs of the cars on that platform in order from front to end, separated by a single space.ENTER 1 10: Platform 1 has [10].ENTER 1 20: Platform 1 has [10, 20].ENTER 2 30: Platform 2 has [30].MERGE 2 1: Platform 1 has [10, 20, 30], Platform 2 is empty. (Source=2, Dest=1)CHECK 1 30 1: Start at 30, move 1 step towards the front -> reaches 20. Output 20.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.REVERSE 1: Platform 1 has [30, 20, 10].CHECK 1 10 2: Start at 10, move 2 steps towards the front -> reaches 30. Output 30.ENTER 3 40: Platform 3 has [40].SPLIT 1 20 2: Train on Platform 1 is split before 20. Platform 1 becomes [30], Platform 2 becomes [20, 10].MERGE 3 2: Platform 2 becomes [20, 10, 40], Platform 3 is empty. (Source=3, Dest=2)