#B4324. Manipulate a Doubly Linked List
Manipulate a Doubly Linked List
Manipulate a Doubly Linked List
You are given \(N\) nodes with labels \(1\) to \(N\) arranged in order in a doubly linked list. Initially, the list is ordered from left to right as \(1, 2, \dots, N\). Then, you are given \(M\) commands to modify the list. All operations are guaranteed to be legal.
| Command | Meaning |
|---|---|
| \(1\ x\ y\) | Remove node \(x\) from its current position and insert it to the left of node \(y\). (If \(x = y\), ignore this command.) |
| \(2\ x\ y\) | Remove node \(x\) from its current position and insert it to the right of node \(y\). (If \(x = y\), ignore this command.) |
| \(3\ x\) | Delete node \(x\) from the list. (If node \(x\) is already deleted, ignore this command.) |
After processing all commands, output the labels of the nodes that remain in the list from left to right.
inputFormat
The first line contains two integers \(N\) and \(M\) which represent the number of nodes and the number of commands respectively.
The following \(M\) lines each contain a command in one of the following formats:
- \(1\ x\ y\)
- \(2\ x\ y\)
- \(3\ x\)
outputFormat
Output the labels of the remaining nodes in the list from left to right, separated by spaces.
sample
5 3
1 4 3
2 2 5
3 31 4 5 2