Background

Special for beginners, ^_^

Description

小J有很多空白的球和一个袋子。最初，袋子是空的。

小J将会作出Q个操作，具体如下：

操作1 在白球上写一个数字Xi然后扔进袋子里；

操作2 将袋子里所有球的数字都加上Xi；

操作3 输出袋子里最小的数字并把它从袋子里取出。

Q<=2*100000

xi<=1e9

Format

Input

输入Q个操作 ，接下来的Q行，每行一个操作，可以是操作1，操作2或操作3，具体格式如 1 5 ，表示操作1 在白球上写一个数字5然后扔进袋子里；

Output

针对每个操作3，输出结果。

Samples

5
1 3
1 5
3
2 2
3

3
7

Limitation

1s, 256024KiB for each test case.