HM213 打饭窗口

来源： 第 213 集 queue容器-基本概念

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

食堂窗口只有一条队伍，它符合**先进先出**：先排进来的人先打到饭。这和只能从同一端进出的栈正好相反——栈是先进后出。

队伍有**两个口**，方向固定，不允许插队：

• 队尾只能进数据，这个过程叫入队，对应 push；
• 队头只能出数据，这个过程叫出队，对应 pop。

队头元素叫 front，队尾元素叫 back。外界**只能看见这两端**，中间的人看不见。若想看见原来排在第二位的人，必须先让队头出队，队伍因此被改掉。遍历不允许改容器，所以队列也不允许遍历。

还可以查询队伍是否为空（empty）以及当前人数（size）。

先把 \(n\) 个人按到达顺序入队，再执行 \(q\) 条指令：

• 1 x：编号 \(x\) 的人从队尾入队；
• 2：队头出队，输出出队编号；若队伍已空，输出 NONE；
• 3：输出队头和队尾；若空，输出 EMPTY；
• 4：先输出当前 size，再输出 empty 为真则 YES 否则 NO；
• 5 k：试图在**不改队**的前提下看见从队头往后数第 \(k\) 个人（\(k=1\) 就是队头）。若队空，输出 EMPTY；若 \(k=1\)，输出队头；若 \(k>1\)，输出 FORBIDDEN（中间位置不可见，即使 \(k\) 恰好指向队尾也不行——队尾只能用专门的 back 查看）；
• 6：不断从队头出队直到变空，按出队顺序输出剩余所有人。这会改掉队伍。若已经为空，输出空行。

输入格式

第一行两个整数 \(n\)、\(q\)。

第二行 \(n\) 个整数，按顺序入队。当 \(n=0\) 时本行可以是空行。

接下来 \(q\) 行，每行一条指令。

输出格式

按指令依次输出。2、3、4、5、6 各占一行。同一行内多个整数用单个空格分隔，行末换行。

样例

输入 #1

4 7
10 20 30 40
3
4
5 1
5 2
2
3
6

输出 #1

10 40
4 NO
10
FORBIDDEN
10
20 40
20 30 40

输入 #2

0 4

3
4
5 1
2

输出 #2

EMPTY
0 YES
EMPTY
NONE

说明

\(0 \le n \le 1000\)，\(1 \le q \le 2000\)，\(1 \le k \le 10^9\)，编号绝对值不超过 \(10^9\)。

样例 #1：四人入队后只能看见队头 \(10\) 和队尾 \(40\)；不改队时从队头数第 \(2\) 人不可见。出队一人后队头变成 \(20\)，再把剩余三人按先进先出弹出。样例 #2 一开始就是空队伍。