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

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

题目描述

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

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

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

输入格式

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

输出格式

对于每次查询,输出一行 x x x 个数,每个数中间以空格间隔,按从小到大顺序排列;如果区间内小于 k k k 的数不足 x x x 个,输出 −1 -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\}{1,2,3}
第一次操作修改后的序列为 {2,2,3}\{2,2,3\}{2,2,3}
第二次操作查询时,区间内最小的 333 个数依次为 2,2,32,2,32,2,3,因为 333 不小于 111 所以答案为 −1-11
第三次操作查询时,区间内最小的 111 个数为 222,因为 222 不小于 222 所以答案为 −1-11
第四次操作查询时,区间内最小的 222 个数依次为 2,22,22,2,因为 222 小于 333 所以答案为 2,22,22,2

数据范围与提示

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

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