#329. [ZJOI2013] K大数查询

[ZJOI2013] K大数查询

[ZJOI2013] K大数查询

题目描述

你需要维护 nn 个可重整数集,集合的编号从 11nn。 这些集合初始都是空集,有 mm 个操作:

  • 1 l r c:表示将 cc 加入到编号在 [l,r][l,r] 内的集合中
  • 2 l r c:表示查询编号在 [l,r][l,r] 内的集合的并集中,第 cc 大的数是多少。

注意可重集的并是不去除重复元素的,如 {1,1,4}{5,1,4}={1,1,4,5,1,4}\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}

输入格式

第一行两个正整数 n,mn,m,表示集合个数和操作个数。 接下来 mm 行,每行四个整数表示一次操作。

输出格式

对于每个 22 操作,输出一行一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

1
2
1

提示

【样例说明】 第 11 次操作在 1,21,2 号集合中分别加入了一个 11。 第 22 次操作在 1,21,2 号集合中分别加入了一个 22。 第 33 次操作查询 11 号集合中第 22 大的数,答案为 11。 第 44 次操作查询 11 号集合中第 11 大的数,答案为 22。 第 55 次操作查询 1,21,2 号集合的并集 {1,2,1,2}\{1,2,1,2\} 中第 33 大的数,答案为 11

【数据范围】 1n,m5×1041 \le n,m \le 5\times 10^4 1l,rn1\le l,r \le n 11 操作中 cn|c|\le n 22 操作中 1c<2631\le c < 2^{63}