题目描述

我们有一个初始为空的整数多重集 $S$。

给定 $Q$ 个查询，请按照顺序处理它们。每个查询属于以下类型之一。

• 1 x：将 $x$ 插入到 $S$ 中。

• 2 x c：从 $S$ 中删除 $x$，删除次数为 $m = \min(c, ($ $S$ 中包含的 $x$ 的数量))$。

• 3：输出 $S$ 中的最大值减去最小值。保证在给定该查询时，$S$ 不为空。

约束条件

• $1 \leq Q \leq 2\times 10^5$
• $0 \leq x \leq 10^9$
• $1 \leq c \leq Q$
• 当提供类型为 3 的查询时，$S$ 不为空。
• 输入中的所有值都是整数。

输入格式

输入以标准输入形式给出，格式如下：

$Q$ $query_1$ $\vdots$ $query_Q$

$query_i$ 表示第 $i$ 个查询，其格式如下：

$1$ $x$ $2$ $x$ $c$ $3$

输出格式

按给定顺序，以换行符分隔的形式输出类型为 3 的查询的答案。

示例输入 1

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

示例输出 1

1
5
4

多重集 $S$ 的变化如下。

• 第一个查询：将 $3$ 插入到 $S$ 中。此时，$S$ 为 $\\lbrace 3 \\rbrace$。
• 第二个查询：将 $2$ 插入到 $S$ 中。此时，$S$ 为 $\\lbrace 2, 3 \\rbrace$。
• 第三个查询：$S$ 中的最大值为 $3$，最小值为 $2$，因此输出 $3-2=1$。
• 第四个查询：将 $2$ 插入到 $S$ 中。此时，$S$ 为 $\\lbrace 2,2,3 \\rbrace$。
• 第五个查询：将 $7$ 插入到 $S$ 中。此时，$S$ 为 $\\lbrace 2, 2,3, 7\\rbrace$。
• 第六个查询：$S$ 中的最大值为 $7$，最小值为 $2$，因此输出 $7-2=5$。
• 第七个查询：由于 $S$ 中有两个 $2$，且 $\\min(2,3) = 2$，因此从 $S$ 中删除 $2$ 两次。此时，$S$ 为 $\\lbrace 3, 7\\rbrace$。
• 第八个查询：$S$ 中的最大值为 $7$，最小值为 $3$，因此输出 $7-3=4$。

示例输入 2

4
1 10000
1 1000
2 100 3
1 10

示例输出 2

如果给定的查询中不包含类型为 3 的查询，则不打印任何内容。