#1102. 「模板」文艺线段树

内存限制:64 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Quank123Wip

题目描述

维护一个数据结构,支持下面三种操作:

  • 1 k k 插入序列
  • 2 k 将序列中的一个 k 删除
  • 3 k 查询序列中第 k 小的数

输入格式

第一行一个数 n, m ,分别表示 k 的值域和操作数。

接下来的 m 行,每行两个整数 op, k ,意义见题目描述。

输出格式

对于每个操作 3 ,在单独的一行输出一个整数 x ,表示当前的序列中第 k 小的数。

样例

输入样例

10 5
1 2
1 3
3 2
2 2
3 1

输出样例

3
3

数据范围与提示

对于 100\% 的数据, n, m\leq 1e8