题目描述

我们有一个整数的多重集$S$，最初为空。给定$Q$个查询，按顺序处理它们。每个查询是以下三种类型之一：

1. 1 x：将$x$插入$S$中。

2. 2 x c：从$S$中移除$m$个$x$，其中$m = min$($c$, $S$中$x$的数量)。

3. 3：输出($S$的最大值) - ($S$的最小值)。保证执行此查询时$S$非空。

输入格式

输入从标准输入中给出，格式如下：
$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$
$query_i$表示第$i$个查询，格式为以下之一：
1 x
2 x c
3

输出格式

对于每个类型$3$的查询，按顺序输出结果，每个结果占一行。

样例

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

1
5
4

4
1 10000
1 1000
2 100 3
1 10

1

样例解释

【样例1说明】
多重集$S$的变化过程如下：

1. 插入3，S = {3}

2. 插入2，S = {2, 3}

3. 输出3 - 2 = 1

4. 插入2，S = {2, 2, 3}

5. 插入7，S = {2, 2, 3, 7}

6. 输出7 - 2 = 5

7. 移除两个2，S = {3, 7}

8. 输出7 - 3 = 4

【样例2说明】
如果给定的查询不包含类型$3$，则不应输出任何内容。

数据范围

$1 ≤ Q ≤ 2×10^5$
$0 ≤ x ≤ 10^9$
$1 ≤ c ≤ Q$
当给出类型$3$的查询时，$S$非空。
所有输入值都是整数

来源

• AtCoder ABC253C