题目描述

有一个售票窗口，队伍初始为空。接下来有 $q$ 个事件：

• L name：编号为 name 的同学从队首插队；
• R name：编号为 name 的同学从队尾排队；
• FL：队首同学买完票离开，如果队伍为空则输出 Empty；
• FR：队尾同学买完票离开，如果队伍为空则输出 Empty。

对于每个离开事件，如果队伍非空，请输出离开的同学编号；否则输出 Empty。

本题用于练习 deque<string>，感受双端队列两端都能插入和删除的特点。

输入格式

第一行一个整数 $q$。

接下来 $q$ 行，每行一个事件。

输出格式

对于每个 FL 或 FR 事件，输出一行结果。

样例

7
R Alice
R Bob
L Cindy
FL
FR
FR
FL

Cindy
Bob
Alice
Empty

数据范围与提示

对于 $100\%$ 的数据，$1 \le q \le 100000$，name 只包含大小写英文字母和数字，长度不超过 $20$。