P1005

[NOI2004]郁闷的出纳员

[NOI2004]郁闷的出纳员

OIER 公司是一家拥有众多员工的大型专业软件公司。作为一名出纳员,你需要统计每位员工的工资。

公司的老板经常调整员工的工资:心情好时,他可能给所有员工增加相同数额的工资;心情不好时,他也可能扣除所有员工相同数额的工资。

所有员工的工资下界相同。一旦某位员工的工资低于合同规定的工资下界,他就会立刻离开公司,并且不会再次回来。员工离开时,需要删除其工资档案;公司招聘新员工时,则需要为其建立新的工资档案。

老板还会询问当前工资第 kk 高的员工能拿到多少工资。请编写一个程序,维护公司的员工工资档案并回答这些询问。

输入格式

第一行包含两个非负整数 nn 和 min\mathrm{min},分别表示接下来的命令数量和统一规定的工资下界。

接下来 nn 行,每行包含一条命令。命令分为以下四种:

命令格式作用
I 命令I kI\ k新建一份初始工资为 kk 的员工工资档案。
A 命令A kA\ k将所有员工的工资增加 kk。
S 命令S kS\ k将所有员工的工资扣除 kk。
F 命令F kF\ k查询当前第 kk 高的工资。

如果新员工的初始工资低于工资下界,则忽略对应的 I 命令,不为其建立工资档案。该员工也不计入最终输出的离职员工总数。

执行 S 命令后,工资低于工资下界的员工将立刻离开公司,并删除其工资档案。

I、A、S 命令中的 kk 为非负整数,F 命令中的 kk 为正整数。初始时公司中没有员工。

输出格式

对于每条 F 命令,输出一行一个整数,表示当前第 kk 高的工资。如果 kk 大于当前员工人数,则输出 −1-1。

最后一行输出一个整数,表示离开公司的员工总数,不包括因初始工资低于工资下界而未被录用的员工。

样例输入

9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2

样例输出

10
20
-1
2

数据范围

  • nn 和 min\mathrm{min} 均为非负整数;
  • I 命令的数量不超过 10510^5;
  • A 命令与 S 命令的总数量不超过 100100;
  • F 命令的数量不超过 10510^5;
  • 每次工资调整的数额不超过 10310^3;
  • 新员工的初始工资不超过 10510^5;
  • I、A、S 命令中的 kk 为非负整数,F 命令中的 kk 为正整数。

来源与许可

本题为 NOI 2004 试题「郁闷的出纳员」,题面与测试数据整理自 BZOJ。

样例 1

输入

9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2

输出

10
20
-1
2