CF1547C Pair Programming

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, \dots, a_n$ 的顺序执行操作。 Polycarp 总共工作了 $m$ 分钟，执行的操作序列为 $[b_1, b_2, \dots, b_m]$。如果 $b_j = 0$，他就在文件末尾添加一行新内容。如果 $b_j > 0$，他就修改第 $b_j$ 行。Polycarp 必须严格按照 $b_1, b_2, \dots, 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$）。

对于每组测试数据，输出任意一个合法的 Monocarp 和 Polycarp 的共同操作序列，长度为 $n + m$。如果不存在这样的序列，输出 $-1$。

由 ChatGPT 4.1 翻译