上帝的集合

题目描述

现在上帝有一个空集合，现在他命令你为他执行下列三种操作 $n$ 次，他每次会给你一个操作类型 $op$。

操作1：向集合中插入一个整数 $x$;

操作2：将集合中所有的数加上 $x$;

操作3：输出集合中最小的数，并从集合中将他删除，如果存在多个最小的整数，任意选择一个即可;

输入格式

第一行输入一个整数 $n$；

接下来的 $n$ 行，每行的输入如下所示。第一个数代表 $op$，如果 $op=1$ 或 $op=2$，第二个数代表 $x_i$：

$1$ $x_i$

$2$ $x_i$

$3$

输出格式

如果 $op=3$，请输出集合中的最小值。

样例输入

7
1 2
1 1
3
1 3
2 5
3
3

样例输出

1
7
8

数据范围

$2 \leq n \leq 10^6$, $1 \leq x_i \leq 10^{12}$