#P18001. Apparently Make UTPC

Apparently Make UTPC

Apparently Make UTPC

给定三个正整数序列 A=(A1,…,AX)A=(A_1,\ldots,A_X)、B=(B1,…,BY)B=(B_1,\ldots,B_Y)、C=(C1,…,CZ)C=(C_1,\ldots,C_Z),且 X≤Y≤ZX\le Y\le Z。

请重新排列 CC,使 AA 和 BB 都是排列后 CC 的连续子序列。两次出现的位置可以重叠。如果存在可行排列,求其中字典序最小的一个。

输入格式

第一行一个整数 TT,表示测试用例数。每个测试用例包含四行:

X Y Z
A1 A2 ... AX
B1 B2 ... BY
C1 C2 ... CZ

输出格式

每个测试用例输出一行。无解输出 -1;有解输出字典序最小的重排后的 CC,相邻元素之间用空格分隔。

数据范围

所有输入均为整数。1≤T≤1051\le T\le10^5,1≤X≤Y≤Z≤2×1051\le X\le Y\le Z\le2\times10^5,1≤Ai,Bi,Ci≤Z1\le A_i,B_i,C_i\le Z。单个输入文件中所有测试用例的 X+Y+ZX+Y+Z 之和不超过 4×1054\times10^5。

样例 1

输入

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

输出

2 1 4 3
4 3 2 1
-1