God's Set

Problem Description

God starts with an empty set. He then asks you to perform $n$ operations of three kinds, each given by an operation type $op$:

• Operation 1: insert an integer $x$ into the set.
• Operation 2: add $x$ to every number in the set.
• Operation 3: output the smallest number in the set and delete it. If several smallest integers exist, you may delete any one of them.

Input Format

The first line contains an integer $n$.

Each of the following $n$ lines has the format below. The first number is $op$; if $op = 1$ or $op = 2$, the second number is $x_i$:

1 x_i
2 x_i
3

Output Format

For every operation of type 3, output the minimum value in the set at that moment.

Sample Input

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

Sample Output

1
7
8

Constraints

$2 \leq n \leq 10^6$

$1 \leq x_i \leq 10^{12}$