提示: 欢迎访问OurACM平台。
Problem 1741 Book Shelf II

Accept: 18    Submit: 82
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

oaiei是一个非常喜欢读书的孩子 ;) ,他有一个特别的书架,书架上摆放着他买的新书。当他决定要阅读某本图书时,他就把书从书架中取出,这时书架上就出现了空位,他会立即整理这些图书使图书之间不出现空位。oaiei总是将新书从左边塞入,由于书架的宽度是有限的,新加入的书可能把书架上另一端的图书挤出来。

oaiei的记忆力不好 ;( ,他需要你的帮助,给你一系列的操作,请你计算出书架上摆放有几本图书,并把它们的编号按照从左到右的顺序输出。一共有三种操作:

  • 添加操作A id w:从书架的左边塞入一本编号为id的图书,该图书的宽度为w,并向右推以确保该图书摆放在书架上。如果书架上图书的总宽度超过书架的宽度,那么不完全在书架内的图书将会从书架上掉下来。任何一本书的宽度都不会超过书架的宽度。如果编号为id的图书已经在书架上,则该操作无效。
  • 删除操作R id:从书架上拿走一本编号为id的图书。如果编号为id的图书不在书架上,则该操作无效。
  • 结束操作E:操作结束。

Input

有多组输入数据,输入数据的第一行是一个整数N(1≤N≤100,000),表示书架的宽度,当N=-1时,所有数据结束。紧接着是一系列的操作,添加操作的格式如下:

A id w

其中id是图书的编号,w是图书的宽度(0 < id≤100,000,0 < w≤N)。

删除操作的格式如下:

R id

其中id为图书的编号(0 < id≤100,000)。

字符‘E’表示操作结束。

需要注意的是,从书架上拿下编号为id的图书后再放一本编号为id的图书,它们的宽度可能不同。操作数不会超过200,000。

Output

对于每组输入数据,输出一个整数S表示书架上图书的数量,接下来一行按照从左到右的顺序输出书架上图书的编号(编号之间有一个空格,最后一个编号后不需要空格)。

Sample Input

5 A 1 1 A 2 1 A 3 1 R 2 A 2 2 A 5 1 R 5 R 4 A 6 1 A 7 4 E 5 E 3 A 1 2 A 2 1 R 3 A 2 3 E -1

Sample Output

2 7 6 0 2 2 1

Source

oaiei

Submit  Back  Status  Discuss