Description

Farmer John（以下简称 FJ）的 N 头奶牛（用 1…N 编号）在直线上排队。一开始，这条线上没有任何奶牛，随着时间的推移，奶牛们会一个接一个地站到队伍的左边或右边。又过了一会儿，某些奶牛会从队伍里离开，去吃自己最喜欢的草料。

FJ 无法跟踪每一头奶牛，于是，他想让你来帮助他。

奶牛以1…N 的顺序排队，并且离开的奶牛不会再次回来。数据将会给出 S（1≤S≤100000） 条指令，各占一行，分两种：

• A 头奶牛加入了队列（还有一个参数，表示从左加入还是从右加入）；
• K 头奶牛从左边或者右边离开了队列（还有两个参数，分别表示从左离开还是从右离开和离开多少头奶牛）。

输入的命令一定是可以执行的。

所有的操作结束后，你的程序应该以从左到右的顺序输出这个奶牛队列。数据保证最后的队列不空。

Input Format

• 第 1 行：单独一个整数 S。
• 第 2…S+1 行：第 i+1 行会有一条命令，有以下几种：
  • A L：一头奶牛从队列左边加入；
  • A R：一头奶牛从队列右边加入；
  • D L K：K 头奶牛从队伍左边离开；
  • D R K：K 头奶牛从队伍右边离开。

Output Format

• 第 1…?? 行：从左到右输出最后的奶牛队列，一个奶牛编号占一行。

10 
A L 
A L 
A R 
A L 
D R 2 
A R 
A R 
D L 1 
A L 
A R

7 
2 
5 
6 
8

Hint

以下为输入的命令及对应的队列：

• A L：1；
• A L：2,1；
• A R：2,1,3；
• A L：4,2,1,3；
• D R 2：4,2；
• A R：4,2,5；
• A R：4,2,5,6；
• D L 1：2,5,6；
• A L：7,2,5,6；
• A R（最终序列）：7,2,5,6,8。

Source

数据结构 模拟 双端队列 USACO