题目描述

你需要维护一个双端队列，并支持一种特殊操作：翻转方向。

初始时队列为空，方向为正常。接下来有 $q$ 次操作：

• PUSH x：如果方向正常，将 $x$ 加到队尾；如果方向翻转，将 $x$ 加到队首；
• POP：如果方向正常，从队首弹出一个元素；如果方向翻转，从队尾弹出一个元素。若队列为空，输出 Empty；否则输出被弹出的元素；
• REV：翻转当前方向；
• FRONT：询问当前方向下的队首元素。若队列为空，输出 Empty。

注意：REV 不需要真的把整个队列倒过来，只需要改变当前方向。

输入格式

第一行一个整数 $q$。

接下来 $q$ 行，每行一个操作。

输出格式

对于 POP 和 FRONT 操作，输出一行结果。

样例

9
PUSH 1
PUSH 2
FRONT
REV
FRONT
PUSH 3
POP
REV
POP

1
2
3
1

数据范围与提示

对于 $100\%$ 的数据，$1 \le q \le 100000$，$|x| \le 10^9$。

提示：可以用一个布尔变量记录当前方向，再决定操作队首还是队尾。