← 返回题目列表

Codeforces · 1547/C

C. 结对编程

中文机器翻译题面 查看原题

Monocarp 和 Polycarp 正在学习新的编程技术。现在他们决定尝试结对编程。

据了解,他们在同一个文件上一起工作了 $$$n + m$$$ 分钟。每分钟只有一个人对文件进行一次更改。在开始之前,文件中已经写入了 $$$k$$$ 行。

每分钟,其中就有一个执行以下两个操作之一:在文件末尾添加新行或更改其中一行。

Monocarp 总共工作了 $$$n$$$ 分钟并执行了一系列操作 $$$[a_1, a_2, \dots, a_n]$$$。如果 $$$a_i = 0$$$,那么他会在文件末尾添加一个新行。如果 $$$a_i > 0$$$,那么他会更改编号为 $$$a_i$$$ 的行。 Monocarp 严格按照以下顺序执行操作:$$$a_1$$$,然后 $$$a_2$$$,...,$$$a_n$$$。

Polycarp 总共工作了 $$$m$$$ 分钟并执行了一系列动作 $$$[b_1, b_2, \dots, b_m]$$$。如果 $$$b_j = 0$$$,那么他会在文件末尾添加一个新行。如果 $$$b_j > 0$$$,则他更改带有数字 $$$b_j$$$ 的行。波利卡普严格按照以下顺序执行动作:$$$b_1$$$,然后$$$b_2$$$,...,$$$b_m$$$。

恢复长度为 $$$n + m$$$ 的常见操作序列,以便所有操作都是正确的 - 不应该对尚不存在的行进行任何更改。请记住,在公共序列中,Monocarp 的动作应形成子序列 $$$[a_1, a_2, \dots, a_n]$$$ ,而 Polycarp 的动作应形成子序列 $$$[b_1, b_2, \dots, b_m]$$$。他们可以在计算机上任意多次替换对方。

让我们看一个例子。假设 $$$k = 3$$$。 Monocarp 首先更改了数字 $$$2$$$ 的行,然后添加了一个新行(因此,$$$n = 2, \: a = [2, 0]$$$)。 Polycarp 首先添加了一个新行,然后用数字 $$$5$$$ 更改了该行(因此,$$$m = 2, \: b = [0, 5]$$$)。

由于文件的初始长度为 $$$3$$$,为了让 Polycarp 更改行号 $$$5$$$ 必须预先添加两行新行。在本例中,正确的更改顺序示例为 $$$[0, 2, 0, 5]$$$ 和 $$$[2, 0, 0, 5]$$$。更改 $$$[0, 0, 5, 2]$$$ (操作顺序错误)和 $$$[0, 5, 2, 0]$$$ ($$$5$$$ 行尚无法编辑)不正确。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$)。然后是 $$$t$$$ 测试用例。每个测试用例之前都有一个空行。

每个测试用例包含三行。第一行包含三个整数 $$$k$$$、$$$n$$$、$$$m$$$ ($$$0 \le k \le 100$$$、$$$1 \le n、m \le 100$$$) — 文件中的初始行数以及 Monocarp 和 Polycarp 的更改序列的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 300$$$)。

第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$0 \le b_j \le 300$$$)。

输出

对于每个测试用例,打印长度为 $$$n + m$$$ 的 Monocarp 和 Polycarp 操作的任何正确公共序列,如果这样的序列不存在,则打印 -1。

示例

输入 #1

5

3 2 2
2 0
0 5

4 3 2
2 0 5
0 6

0 2 2
1 0
2 3

5 4 4
6 0 8 0
0 7 0 9

5 4 1
8 7 8 0
0

输出 #1

2 0 0 5 
0 2 0 6 5 
-1
0 6 0 7 0 8 0 9
-1