题目描述
众所周知，ZQC 是个很喜欢收纳手办的大佬，他平时在写题前会先扫视一下桌面上排开的小姐姐们以获取灵感。假设他有 n(1≤n≤5×10
5
) 个手办，小手办们排成一排，每个手办按照入手批次从第
1
个到第
n
个被贴上了一个标号a
i
(1≤a
i
≤10
9
)。有两个熊孩子到 ZQC 家里玩，熊孩子 A 不断地改掉标签并不停地提问熊孩子 B。由于熊孩子 B 太笨，经常回答不上来，熊孩子 A 表示很生气，ZQC 为了世界和平（把熊孩子哄高兴好让它们帮忙把标签贴回去），大发慈悲地帮助熊孩子 B 回答一系列问题。假设一共 m(1≤m≤5×10
5
) 次操作，两种操作分别为：
1 a b k 将数列
[a, b]
这个区间中所有比 k(1≤k≤109) 小的数改为
k
；
2 a b k x 查询
[a, b]
的区间中比 k(1≤k≤109) 小的最小的x(1≤x≤105) 个数。
ZQC 最后成功维护了世界正义，请在每次查询时输出熊孩子 A 所要的回答。
输入
第一行为
n
，表示手办总数。
接下来一行
n
个数a
1
,a
2
,...,a
n
，a
i
表示第
i
个手办的标号。
接下来一行为
m
，表示总操作数。
接下来
m
行，格式见「题目描述」。
输出
对于每次查询，输出一行
x
个数，每个数中间以空格间隔，按从小到大顺序排列；如果区间内小于
k
的数不足
x
个，输出
-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}；
第一次操作修改后的序列为{2,2,3}；
第二次操作查询时，区间内最小的 3 个数依次为
2,2,3
，因为
3
不小于
1
所以答案为
-1
；
第三次操作查询时，区间内最小的
1
个数为 2，因为
2
不小于
2
所以答案为
-1
；
第四次操作查询时，区间内最小的 2 个数依次为
2,2
，因为
2
小于 3 所以答案为
2,2
。
数据范围与提示
∑x≤5×106
输出总数量不超过 2×106 个整数，包括
-1
。
出题人的关怀：由于输入规模较大，建议使用读入优化。
来源/分类
LibreOJ β Round