题目描述

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

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

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$。

数据范围与提示

$\sum{x}\leq 5\times 10^6$
输出总数量不超过 $2\times 10^6$ 个整数，包括 $-1$。

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