栈队（staque）

• 题目 PID：NC26JB
• 时间限制：1 秒
• 内存限制：512 MiB

问题背景

小 S 学了数据结构栈和队列，他觉得太简单了，于是想将两者结合起来，定义一种新的数据结构栈队。它有时候是栈，有时候是队列。现在小 S 要测试这种数据结构的运作过程。

问题描述

一个栈队初始时是一个栈，即如众所周知的那样，有栈顶和栈底，且初始时栈是空的。小 S 会依次发出 $q$ 条指令，指令共有如下 3 种类型：

• 指令 A：表示栈队类型切换。具体地，如当前是栈，则变为队列，原先的栈顶视为队首，原先的栈底视为队尾；如当前是队列，则反之（队首视为栈顶，队尾视为栈底）。
• 指令 B：表示将数值 $i$ 入栈/入队（如当前是栈，则从栈顶加入；否则从队尾加入）。其中 $i$ 为当前是第几次执行指令 B。
• 指令 C：表示出栈/出队（如当前是栈，则从栈顶弹出；否则从队首弹出）。输出被弹出的数值。特别地，如当前栈队为空，则输出 -1，并且栈队内容不变（仍然为空）。

输入格式

从文件 staque.in 中读取数据。

第 1 行一个正整数 $q$。

第 2 行一个长度为 $q$ 的字符串，只包含 A、B、C，表示依次进行的指令类型。

输出格式

输出到文件 staque.out。

若干行，每行一个整数，依次表示每个 C 类指令的输出。

文件读写示例

freopen("staque.in", "r", stdin);
freopen("staque.out", "w", stdout);

样例 1

9
CBBCABBCC

-1
2
1
3

样例 1 解释

以下给出了每条指令执行后，当前栈队的类型和元素。左侧是栈底/队尾。

C  空栈（输出 -1）
B  栈：1
B  栈：1 2
C  栈：1（输出 2）
A  队列：1
B  队列：3 1
B  队列：4 3 1
C  队列：4 3（输出 1）
C  队列：4（输出 3）

数据规模与约定

• 对于 $20\%$ 的数据，$q=3$。
• 对于另 $20\%$ 的数据，没有指令 A。
• 对于另 $20\%$ 的数据，第 1 个指令为 A，剩余的指令中不再有指令 A。
• 对于 $100\%$ 的数据，$1\leq q\leq100000$。