#504. 「LibreOJ β Round」ZQC 的手办

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

题目描述

众所周知,ZQC 是个很喜欢收纳手办的大佬,他平时在写题前会先扫视一下桌面上排开的小姐姐们以获取灵感。假设他有 n(1n5×105) n(1 \leq n \leq 5\times 10 ^ 5) 个手办,小手办们排成一排,每个手办按照入手批次从第 1 1 个到第 n n 个被贴上了一个标号 ai(1ai109) a_i(1 \leq a_i \leq 10 ^ 9) 。有两个熊孩子到 ZQC 家里玩,熊孩子 A 不断地改掉标签并不停地提问熊孩子 B。由于熊孩子 B 太笨,经常回答不上来,熊孩子 A 表示很生气,ZQC 为了世界和平(把熊孩子哄高兴好让它们帮忙把标签贴回去),大发慈悲地帮助熊孩子 B 回答一系列问题。假设一共 m(1m5×105) m(1 \leq m \leq 5\times 10 ^ 5) 次操作,两种操作分别为:

  • 1 a b k \texttt{1 a b k} 将数列 [a,b] [a, b] 这个区间中所有比 k(1k109) k(1 \leq k \leq 10 ^ 9) 小的数改为 k k
  • 2 a b k x \texttt{2 a b k x} 查询 [a,b] [a, b] 的区间中比 k(1k109) k(1 \leq k \leq 10 ^ 9) 小的最小的 x(1x105) x(1 \leq x \leq 10^5) 个数。

ZQC 最后成功维护了世界正义,请在每次查询时输出熊孩子 A 所要的回答。

输入格式

第一行为 n n ,表示手办总数。
接下来一行 n n 个数 a1,a2,...,ana_1,a_2,...,a_nai a_i 表示第 ii 个手办的标号。
接下来一行为 m m ,表示总操作数。
接下来 m m 行,格式见「题目描述」。

输出格式

对于每次查询,输出一行 x x 个数,每个数中间以空格间隔,按从小到大顺序排列;如果区间内小于 k k 的数不足 x x 个,输出 1 -1

样例

样例输入

3
1 2 3
4
1 1 2 2
2 1 3 1 3
2 1 3 2 1
2 1 3 3 2

样例输出

-1
-1
2 2

样例解释

开始序列为 {1,2,3}\{1,2,3\}
第一次操作修改后的序列为 {2,2,3}\{2,2,3\}
第二次操作查询时,区间内最小的 33 个数依次为 2,2,32,2,3,因为 33 不小于 11 所以答案为 1-1
第三次操作查询时,区间内最小的 11 个数为 22,因为 22 不小于 22 所以答案为 1-1
第四次操作查询时,区间内最小的 22 个数依次为 2,22,2,因为 22 小于 33 所以答案为 2,22,2

数据范围与提示

x5×106\sum{x}\leq 5\times 10^6
输出总数量不超过 2×1062\times 10^6 个整数,包括 1-1

出题人的关怀:由于输入规模较大,建议使用读入优化。