Description
Domo is a super train destroyer, he wants to adjust the train he's driving.
There are two instructions below with the description:
1. AddBack N
The AddBack instructions will be followed by N numbers on the seccond line, representing train carriages that you need to add them at the back of the current train.
2. LinearDelete
Delete carriages using the linear delete rule.
Example of AddBack:
AddBack 5
1 3 2 4 5
makes the train [4, 1] become [4, 1, 1, 3, 2, 4, 5].
AddBack 3
3 1 2
makes a empty train [] become [3, 1, 2].
Linear delete rule:
1. Consider the first carriage as the "DEL" carriage, repeat steps 2~4 until you step out from the back of the train at step 4.
2. Store the index of the DEL carriage in the variable K.
3. Move forward K steps, and assign the carriage after K steps as the new DEL carriage. (If step out from the end of the train, terminate when you finish step 4)
4. Delete the old DEL carriage (the beginning carriage in step 3), and back to step 2 if we haven't stepped out from the end of the train, otherwise terminate.
For example:
suppose the current train is [3, 1, 3, 2, 4, 2, 6, 4, 2, 7, 3, 2] and the instruction is LinearDelete
1. At the beginning, the DEL carriage is '3'.
2. Since DEL carriage is '3', we step forward 3 steps. Hence, the new DEL carriage is '2'.
3. we delete the old DEL carriage.
4. Repeat the procedure until we step out of the train.
In this case, the last movement moves out from the carriage '2' to the outside of the train. Hence, after we delete the '2' carriage, we terminate the instruction.
5. The result will be [1, 3, 4, 6, 2, 7, 3].
The train is empty in the beginning. Given a series of instructions, please print the index of train carriages after all instructions are executed. The first instruction must be AddBack.
This is a partial judge problem, you're asked to implement these 2 functions.
Hint: Carefully maintain Node** head and back!
Input
The input consists of multiple instructions (1 ≤ number of instructions ≤ 103)
the index of AddBack will be positive integers, and:
Testcase 1: 2 ≤ index ≤ 100
Testcase 2: 1 ≤ index ≤ 100
the integer N in AddBack will not greater than 103.
Output
The output only consists of a line denoting the train carriage indices after all the instructions.
It's guaranteed that the output consists of at least one carriage.