You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小$Q$得到了一台神奇的数据处理机，这台机器专门用来处理海量的整数流。虽然机器的运算速度还不错但是它最明显的优点是使用内存极小，不过小$Q$发现，如果处理逻辑过于复杂，机器在处理数据时会出现严重的卡顿,并且在查询的时候总会出现一些错误。
你需要帮助小$Q$实现一个高效的查询模块，确保在极短的时间内完成所有操作。 维护一个初始为空的动态序列，支持以下三类操作：

1. 添加元素$x$：向序列中插入一个整数 $x$。
2. 查询第 $k$ 大 ：输出当前序列中第 $k$ 大的数。保证查询时，序列内元素个数 $\ge k$。
3. 查询大小 ：输出当前序列中元素的总个数

但由于机器本身的查询机制问题,只有第一次的时候会比查询的值和数据本身一样,之后每次查询都会在正确数组的基础上再加上上次查询的正确值但数据本身不变(如上一次查询的是20,这次查询的是10,但机器反馈的查询结果是30,而数据本身依旧是10,并且下一次查询的时候会加上10,但是机器中的数据不发生改变),不管是查询大小或者查询第k大,这种问题总是存在.

输入格式

第一行包含一个整数 $T$，表示操作总次数。
接下来 $T$ 行，每行开头为一个整数 $p$ ($1 \le p \le 3$)。

• 若 $p=1$，后接一个整数 $x$,表示插入一个整数$x$。
• 若 $p=2$，后接一个整数 $k$,表示输出当前数据中第k大的数。
• 若 $p=3$表示查询大小

$1\le T \le 10^{6}$
$0 \le x \le 10^{12}$
$1\le k$ $\le$数据总量
保证相邻两次查询的 $k$ 值之差 $|k_{i} - k_{i-1}| \le 100$

输出格式

对于每个查询第$k$和查询大小的操作，输出一行一个整数。

输入输出样例 #1

输入 #1

5
1 10
3
1 20
2 1
3

输出 #1

1
21
22

说明/提示

样例中第一次操作插入了10,第二次操作查询了大小为1,第三次操作插入了20,第四次操作查询当前第一大的数因为上次查询的正确值是1所以这次查询结果是20+1=21,第五次操作查询大小为2,但上次查询的正确值是20,所以这次查询结果是20+2=22