AT_joi2020_yo1a_c.マージ (Merge)

给定一个长度为 $N$ 的正整数序列 $A=(A_1,\ A_2,\ \ldots,\ A_N)$ 和一个长度为 $M$ 的正整数序列 $B=(B_1,\ B_2,\ \ldots,\ B_M)$。这两个序列都是广义单调递增序列。也就是说，满足 $A_1\leq A_2\leq \cdots\leq A_N$，$B_1\leq B_2\leq \cdots\leq B_M$。

使用如下算法，从这两个序列生成一个长度为 $N+M$ 的正整数序列 $C=(C_1,\ C_2,\ \ldots,\ C_{N+M})$。

1. 初始时 $C$ 为空。
2. 如果 $A$ 和 $B$ 都为空，则算法结束。
3. 如果 $A$ 或 $B$ 其中之一为空，则令 $t$ 为非空的那个序列。如果都不为空，则取首元素较小的序列为 $t$。如果 $A$ 和 $B$ 的首元素相等，则取 $A$ 作为 $t$。
4. 将 $t$ 的首元素添加到 $C$ 的末尾。
5. 从 $t$ 中删除首元素。
6. 返回步骤 2。

给定广义单调递增的正整数序列 $A$ 和 $B$，请编写程序输出按照上述算法生成的正整数序列 $C$。

输入通过标准输入给出，格式如下：

$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_M$

请输出 $N+M$ 行。

第 $k$ 行（$1\leq k\leq N+M$）输出 $C_k$。

限制条件

• $1\leq N\leq 500$。
• $1\leq M\leq 500$。
• $1\leq A_1\leq A_2\leq \cdots\leq A_N\leq 2000$。
• $1\leq B_1\leq B_2\leq \cdots\leq B_M\leq 2000$。

样例解释 1

在执行算法前，$A=(1,2),\ B=(2)$。数列 $C$ 的生成过程如下：

• 数列 $A$ 的首元素为 $1$，数列 $B$ 的首元素为 $2$，因此将 $A$ 的首元素添加到 $C$ 并从 $A$ 中删除。
• 数列 $A$ 的首元素为 $2$，数列 $B$ 的首元素为 $2$，因此将 $A$ 的首元素添加到 $C$ 并从 $A$ 中删除。
• 数列 $A$ 已空，因此将 $B$ 的首元素添加到 $C$ 并从 $B$ 中删除。
• 数列 $A$ 和 $B$ 都为空，算法结束。

算法结束后，数列 $C=(1,2,2)$。

由 ChatGPT 4.1 翻译