该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

After learning about Dancing Links, Longlong found the concept of a "dancing" data structure very cool, so he decided to create a new structure called Dancing Stacks.

The Dancing Stack is essentially a stack that supports the following operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes the current top element from the stack.
• Rotate: Rotates the stack by 180 degrees, reversing the order of all elements in the stack. Specifically, if the elements from top to bottom are $S_0,S_1, \dots ,S_n$, after the rotation, the order will be $S_n, S_{n-1}, \dots, S_0$.
• Swap: Swaps the positions of adjacent elements in the stack. If the stack contains an odd number of elements, the bottom element remains in place. For example, if the elements from top to bottom are $S_0, S_1, \dots, S_n$, after the swap operation,$S_0$ swaps with $S_1$, $S_2$ ​swaps with $S_3$ ​, and so on.

输入格式

The first line contains a positive integer $Q$ ( $1 \le Q \le 2 \times 10^5$ ), representing the total number of operations.
The next $Q$ lines each represent one of the following four formats:

1. 0 x: Push the integerxxx(within the 32-bit signed integer range) onto the stack.
2. 1: Pop the top element from the stack.
3. 2: Perform a rotate operation on the stack.
4. 3: Perform a swap operation on the stack.

输出格式

For every pop operation, output the element that is removed. If the pop operation is invalid (i.e., the stack is empty), output-1.

题目示例数据

19
2
1
0 5
0 3
0 100
0 -2
0 1
2
1
0 32
0 58
3
1
1
1
3
1
2
1

-1
5
32
58
100
1
-2