题目描述

我们有一个整数的多重集 $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$。

接下来 $Q$ 行，每行一个操作，格式如题。

输出格式

按顺序输出每个 $3$ 型询问的答案。

每次回答完要换行。

样例 #1

样例输入 #1

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

样例输出 #1

1
5
4

样例 #2

样例输入 #2

4
1 10000
1 1000
2 100 3
1 10

样例输出 #2

说明/提示

样例说明 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 \le c \le Q \le 2 \times 10^5$；
• $0 \le x \le 10^9$；
• 当给出类型 $3$ 的查询时，$S$ 非空。当输入值都是整数。