Recoupling the Freight Train

A freight train is a singly linked list of wagons; each node's value is the wagon's number, and all numbers are distinct. The yard master applies a list of commands in order:

• ("after", a, b): uncouple wagon a and couple it directly after wagon b, where "after" means one step further from the head in the train's current order. (a != b.)
• ("front", a): uncouple wagon a and make it the new head.
• ("turn",): the whole train is turned around, so its order is reversed.

Every wagon named in a command is in the train. Return the head of the final train. Re-link the existing nodes (each next must be correct at the end); do not build new nodes.

Examples

Input:  head = 1 -> 2 -> 3 -> 4 -> 5,
        commands = [("after", 1, 4), ("turn",), ("front", 3)]
Output: 3 -> 5 -> 1 -> 4 -> 2
Explanation: 2 3 4 1 5, then turned: 5 1 4 3 2, then 3 moves to the front.

Input:  head = 7 -> 8 -> 9, commands = [("turn",), ("after", 9, 7)]
Output: 8 -> 7 -> 9

Input:  head = 6, commands = [("turn",), ("front", 6)]
Output: 6

Constraints

• 0 <= number of wagons <= 3 * 10**4, 0 <= len(commands) <= 3 * 10**4
• Commands other than ("turn",) only appear when the train has at least one wagon.
• Target: O(1) work per command. Searching the train for a wagon, or reversing it, on every command is too slow for the large tests, even with Python list methods.

Goals

• Find any node in O(1) with a dictionary from label to node
• Keep links in both directions so a node can be unhooked without searching for its predecessor
• Reverse a whole chain in O(1) by swapping the roles of the two link directions