题目描述

你有一个空的多重集合（允许元素多次出现），执行以下操作共q次：

• 1 \space x：向集合中新增元素x。

• 2 \space l \space r：查询大小在[l, r]的元素的个数之和。

• 3 \space k：查询集合中第k小的元素，保证k小于等于此时集合大小。

输入描述

第一行一个整数表示q(1 \le n, q \le 2\times10^5)。

接下来q行，每行一个操作。(1 \le op \le 3, 1 \le l \le r \le n, 1 \le x, k \le n)

输出描述

对于每次操作2和3，输出一行结果。

输入样例1

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

输出样例1

2
3
2

本题在《算法中级课》中有详细讲解：https://www.starrycoding.com/course/2