Problem Description
You are hosting a party game where at any point in time, one of two events may occur. The game works with some people in a row. Intially, the row is empty. A total of Q events will occur in the game
- A person joins the line on the far right.
- The left half of the line and the right half of the line swap positions. If there an odd number of people, the left half includes the middle person. For example, 1 2 3 4 5 becomes 4 5 1 2 3
Input
The first line of input will contain three integers, Q
The next Q lines of input contain data for an event.
If the first number in that line is 1, someone is joining the line. The next number is the number of the person joining the line of the far right.
If the first number in that line is 2, the left half of the line and the right half of the line will swap positions
Output
The output should contain a single line of integers, describing the people from left to right
Limits
For all subtasks: 1 ≤ Q ≤ 100 000.
Subtask 1 (20%): Q ≤ 1000.
Subtask 2 (40%): Swaps occur only when the size of the line is even
Subtask 3 (40%): No additional constraints.
Sample Input
7
1 1
1 2
2
1 3
1 4
1 5
2
Sample Output
4 5 2 1 3
Explanation
Persons 1 and 2 are added to the line. Then, they swap positions, the line is now 2 1. Then 3, 4 and 5 are added, the line is now 2 1 3 4 5. Finally, the left half and the right half is swapped, giving 4 5 2 1 3.