#ABC212D. 多重集询问

多重集询问

AT_abc212_d [ABC212D] Querying Multiset

题目描述

\hspace{15pt}高桥君有许多还没有写字的球和一个袋子。最开始袋子是空的,高桥君将依次进行 qq 次操作。每次操作是以下三种之一:

∙ \hspace{23pt}\bullet\,操作 11:在一个还没有写字的球上写下整数 xx,然后把它放进袋子;

∙ \hspace{23pt}\bullet\,操作 22:将袋子里所有球上写的数都加上 xx;

∙ \hspace{23pt}\bullet\,操作 33:从袋子里取出写有最小数字的球(如果有多个,任选一个),记录下这个数字,然后把这个球丢弃。

\hspace{15pt}给定每次操作的类型,以及操作 11、操作 22 中的 xx,请你按照顺序输出每次操作 33 记录下的数字。

输入格式

\hspace{15pt}第一行输入一个整数 q(1≦q≦2×105)q \left(1 \leqq q \leqq 2 \times 10^5\right) 代表操作次数。

\hspace{15pt}此后 qq 行,第 ii 行输入第 ii 个操作,每行先输入一个整数 pi(1≦pi≦3)p_i \left(1 \leqq p_i \leqq 3\right) 代表操作类型,编号同题干:

∙ \hspace{23pt}\bullet\,若 pi=1p_i=1,紧接着在同一行输入一个整数 xi(1≦xi≦109)x_i \left(1 \leqq x_i \leqq 10^9\right) 代表写在新球上的数;

∙ \hspace{23pt}\bullet\,若 pi=2p_i=2,紧接着在同一行输入一个整数 xi(1≦xi≦109)x_i \left(1 \leqq x_i \leqq 10^9\right) 代表给袋中所有球加上的数;

∙ \hspace{23pt}\bullet\,若 pi=3p_i=3,该行只有 pip_i 一个整数。

\hspace{15pt}保证至少存在一次操作 33,并且每次操作 33 执行前,袋子里至少有一个球。

输出格式

\hspace{15pt}对于每一次操作 33,新起一行输出当时记录下的数字。注意,答案可能超出 3232 位整数的范围。

测试样例

5
1 3
1 5
3
2 2
3
3
7

样例 1 解释

\hspace{15pt}高桥君依次进行如下操作:

∙ \hspace{23pt}\bullet\,操作 11(x1=3x_1=3):把写有 33 的球放入袋子,袋中球的数字为 {3}\{3\};

∙ \hspace{23pt}\bullet\,操作 11(x2=5x_2=5):把写有 55 的球放入袋子,袋中球的数字为 {3,5}\{3,5\};

∙ \hspace{23pt}\bullet\,操作 33:取出写有最小数字的球,记录 33,然后丢弃,袋中球的数字为 {5}\{5\};

∙ \hspace{23pt}\bullet\,操作 22(x4=2x_4=2):袋中所有球的数字都加上 22,变为 {7}\{7\};

∙ \hspace{23pt}\bullet\,操作 33:取出写有最小数字的球,记录 77,然后丢弃,袋子变为空。

\hspace{15pt}因此依次输出 33 和 77。

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