题目描述

桌面上有一叠卡牌，初始时从牌堆顶到牌堆底依次为 $1,2,\ldots,n$。

接下来有 $q$ 次操作：

• TOP：将牌堆顶的一张牌拿出，并放到牌堆底；
• BOTTOM：将牌堆底的一张牌拿出，并放到牌堆顶；
• ASK：询问当前牌堆顶的牌编号。

保证执行 TOP 和 BOTTOM 时牌堆非空。

本题用于练习用 deque 模拟牌堆两端移动。

输入格式

第一行两个整数 $n,q$。

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

输出格式

对于每个 ASK 操作，输出一行一个整数，表示当前牌堆顶的牌编号。

样例

5 6
ASK
TOP
ASK
BOTTOM
ASK
TOP

1
2
1

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 100000$，$1 \le q \le 100000$。