AT_utpc2025_a Apparently Make UTPC
题目描述
给定三个长度分别为 $X, Y, Z$ 的正整数数列 $A = (A_1, A_2, \ldots, A_X)$,$B = (B_1, B_2, \ldots, B_Y)$,$C = (C_1, C_2, \ldots, C_Z)$。保证满足 $X \leq Y \leq Z$。
你可以自由地对 $C$ 中的元素进行重新排列,目标是使重排后的 $C$ 同时包含 $A$ 和 $B$ 作为其连续子序列(连续子串)。
请判断能否达成该目标。如果能达成,请输出所有满足条件的重排结果中,字典序最小的那个数列 $C$。
本题包含 $T$ 个测试用例,请分别给出答案。
输入格式
输入由标准输入给出,格式如下:
第一行包含一个整数 $T$,表示测试用例组数;
接下来依次给出 $T$ 个测试用例:
每个测试用例的第一行为三个整数 $X, Y, Z$;
第二行为数列 $A$ 的元素:$A_1, A_2, \ldots, A_X$;
第三行为数列 $B$ 的元素:$B_1, B_2, \ldots, B_Y$;
第四行为数列 $C$ 的元素:$C_1, C_2, \ldots, C_Z$。
输出格式
输出共 $T$ 行。
第 $i$ 行输出第 $i$ 个测试用例的答案:如果无法达成目标,输出 `-1`;如果可以达成,输出重排后满足条件且字典序最小的数列 $C$(元素之间用空格隔开)。
说明/提示
### 样例解释 1
- 对于第 $1$ 个测试用例,重排后满足条件的 $C$ 有两种可能:$(2, 1, 4, 3)$ 和 $(4, 3, 2, 1)$。其中 $(2, 1, 4, 3)$ 的字典序更小,因此输出它。
- 对于第 $2$ 个测试用例,重排后满足条件的 $C$ 只有 $(4, 3, 2, 1)$ 这 $1$ 种可能,因此输出它。
- 对于第 $3$ 个测试用例,无论怎么重排都无法同时包含 $A$ 和 $B$,因此输出 `-1`。
### 数据范围
- 输入数据全为整数
- $1 \leq T \leq 10^5$
- $1 \leq X \leq Y \leq Z \leq 2 \times 10^5$
- $1 \leq A_i \leq Z$
- $1 \leq B_i \leq Z$
- $1 \leq C_i \leq Z$
- 在同一个测试文件中,所有测试用例的 $X + Y + Z$ 之和不超过 $4 \times 10^5$。