题目描述

高桥君有许多空白球和一个空袋子。他将进行 $Q$ 次操作，每次操作是以下三种类型之一：

1. 操作1：在一个空白球上写下整数 $X_i$ ，并将其放入袋中
2. 操作2：将袋中所有球上的数字都加上 $X_i$
3. 操作3：取出袋中数字最小的球（若有多个则任取一个），记录该数字后将球丢弃

请根据给定的操作序列，按顺序输出所有操作 $3$ 记录的数字。

输入格式

输入格式如下：

$Q$

$query_1$

$query_2$

$...$

$query_Q$

每个 $query_i$ 格式为：

操作1：$1$ $X_i$

操作2：$2$ $X_i$

操作3：$3$

输出格式

对每个操作3，输出记录的数字，每个结果占一行。

样例 #1

输入

5
1 3
1 5
3
2 2
3

输出

3
7

样例 #2

输入

6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3

输出

5000000000

提示

数据范围

• $1 \leq Q \leq 2 \times 10^5$
• 操作类型 $1 \leq P_i \leq 3$
• $1 \leq X_i \leq 10^9$
• 保证至少有一个操作3
• 执行操作3时袋中至少有一个球

样例1说明

操作流程：

1. 放入数字3的球
2. 放入数字5的球
3. 取出最小数字3并记录
4. 将袋中数字5的球改为7
5. 取出数字7并记录

样例2说明

注意答案可能超出32位整数范围。