题目描述

OIER 公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。老板经常调整员工的工资：如果他心情好，就可能把每位员工的工资加上一个相同的量；反之，如果心情不好，就可能把他们的工资扣除一个相同的量。

每位员工的工资下界都是统一规定的，记为 min。一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每当一个人离开公司，就要从电脑中把他的工资档案删去；每当公司招聘了一位新员工，就得为他新建一个工资档案。

老板经常询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第 $k$ 多的员工拿多少工资。

你需要编写一个工资统计程序，处理以下命令：

• I k：新建一个工资档案，初始工资为 $k$。如果某员工的初始工资低于工资下界 min，他将立刻离开公司（不计入离开总数）。
• A k：把每位员工的工资加上 $k$。
• S k：把每位员工的工资扣除 $k$。扣除后，如果某些员工的工资低于 min，则这些员工离开公司，并计入离开总数。
• F k：查询当前工资第 $k$ 多的员工所拿的工资数（$k$ 从大到小排序，即第 $1$ 多为最高工资）。如果 $k$ 大于目前员工的数目，则输出 $-1$。

注意：离开公司的员工总数不包括因员工的初始工资低于工资下界而离开公司的情况。

输入格式

第一行有两个非负整数 $n$, min，$n$ 表示下面有多少条命令，min 表示工资的下界；

接下来的 $n$ 行，每行表示一个命令。命令可以是以下四种之一：

• I k
• A k
• S k
• F k

I 命令，A 命令，S 命令中，$k$ 是一个非负整数。F 命令中，$k$ 是一个正整数。

在初始时，可以认为公司中一位员工也没有。

输出格式

输出的行数为 F 命令的条数加一。

对于每条 F 命令，你的程序要输出一行，仅包含一个整数，为当前工资第 $k$ 多的员工所拿的工资数，如果 $k$ 大于目前员工的数目，则输出 $-1$；

输出的最后一行包含一个整数，为离开公司的员工的总数（不包括因员工的初始工资低于工资下界而离开公司的情况）。

样例

输入样例 1

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

输出样例 1

10
20
-1
2

样例解释

初始：min=10，公司为空。

1. I 60：加入工资60，员工集合：{60}。
2. I 70：加入工资70，员工集合：{60,70}。
3. S 50：全体减50，员工集合：{10,20}（60-50=10，70-50=20）。
4. F 2：查询第2多（即第二高），员工工资排序：20,10，第2多是10，输出10。
5. I 30：加入工资30，员工集合：{10,20,30}。
6. S 15：全体减15，员工集合：{-5,5,15}（10-15=-5，20-15=5，30-15=15）。低于min=10的员工：-5和5，他们离开公司，离开总数增加2，并删除他们。员工集合：{15}。
7. A 5：全体加5，员工集合：{20}。
8. F 1：查询第1多，员工工资：20，输出20。
9. F 2：查询第2多，但只有1个员工，输出-1。

最后输出离开总数：2（第6步离开的2人）。

数据范围

• I 命令的条数不超过 $10^5$。
• A 命令和 S 命令的总条数不超过 $100$。
• F 命令的条数不超过 $10^5$。
• 每次工资调整的调整量不超过 $10^3$。
• 新员工的工资不超过 $10^5$。

时间限制：1000 ms
内存限制：524288 KB

提示

由于 A 和 S 命令的总数很少（不超过100），而 I 和 F 命令可能很多，我们可以用相对工资的思想来避免对每个员工都进行加减操作。

设一个全局变量 delta 表示累计调整量（A 命令加 k 则 delta += k，S 命令减 k 则 delta -= k）。每个员工的原始工资为 real = recorded + delta，其中 recorded 是插入时记录的值。

具体做法：

1. 维护一个平衡树（如 multiset 或 Treap/Splay）存储员工的 recorded 值（即插入时的工资减去当时的 delta）。
2. 对于 I k：
   • 如果 k < min，直接忽略（不计入离开）。
   • 否则，插入 k - delta 到平衡树中。
3. 对于 A k：delta += k。
4. 对于 S k：
   • delta -= k。
   • 此时，员工的真实工资 = recorded + delta。需要删除所有 recorded + delta < min 的员工，即 recorded < min - delta。
   • 由于 recorded 在平衡树中是有序的，我们可以不断取出最小的 recorded，如果 recorded < min - delta，则删除并累加离开人数，直到条件不满足。
5. 对于 F k：
   • 如果平衡树大小小于 k，输出 -1。
   • 否则，查询第 k 大的 recorded 值（因为 recorded 从小到大排序时，第 k 大即第 size-k+1 小），然后真实工资 = recorded + delta。

注意：平衡树中存储的是 recorded，即相对于当前 delta 的偏移量。插入时记录 k - delta，查询时加上 delta。

数据结构选择：

• 可以使用 multiset 配合迭代器进行删除和查询第 k 大（需要求第 k 大，可以用 prev(s.end(), k) 找到第 k 大的迭代器）。
• 也可以使用 Treap 或 Splay 直接支持按大小分裂合并，更方便查询第 k 大。

时间复杂度：I 和 F 操作 $O(\log m)$，S 操作可能连续删除多个员工，但总删除次数不超过 I 命令数，因此总复杂度 $O(n \log n)$。

注意：A 和 S 命令的调整量虽然不大，但 delta 可能变得很大（正或负），注意用 long long 存储。