2018 博士生面试机考

C. Reversible Stack

单点时限: 3.0 sec

内存限制: 256 MB

出题人当然是希望出的题目看起来并非毫无意义,于是想方设法给题目配上一些背景故事,使得它看起来不那么无趣。但有时候适得其反。比如当你坐在考场中焦头烂额的时候,眼前又出现一大段的让你感到很困惑的中文,这时候你只会更加焦头烂额。

有这么一种栈,支持三种操作。

  1. 1 X:在栈顶压入元素 $X$。
  2. 2:弹出栈顶元素。
  3. 3:翻转整个栈(栈顶元素到最下面,第二个元素到倒数第二,依次类推)。

要求在每次操作后输出栈顶的元素。如果操作后栈空,输出 $-1$。

输入格式

第一行一个整数 $q$。

接下来每一行为 1 X, 2, 3 这三种之一。$1 \le X \le 10^9$,可能会有相同的数出现。

输入保证操作序列合法:不会对空栈进行操作 2,但可能会进行操作 3。

部分分约定:

  • $30\%$: 没有反转操作;
  • $70\%$: 操作数量不超过 $10^3$;
  • $100\%$: 操作数量不超过 $3 \cdot 10^5$。

输出格式

输出 $q$ 行,每行一个结果。

样例

Input
5
1 1
2
1 3
1 2
2
Output
1
-1
3
2
3
Input
11
1 1
1 2
1 3
1 4
1 5
3
2
2
2
2
2
Output
1
2
3
4
5
1
2
3
4
5
-1