配点: 100 点
問題文
长度 N 的正整数序列 A=(A_1, A_2, \ldots, A_N) 和长度 给出了 M 的正整数序列 B=(B_1, B_2, \ldots, B_M) 。 这两个序列都是大致单调递增的序列。换句话说,A_1 \leqq A_2 \leqq \cdots \leqq A_N, B_1 \leqq B_2 \leqq \cdots \leqq B_M 满意。
从这些序列中,使用以下算法查找长度 生成 N+M 的正整数序列 C=(C_1, C_2, \ldots, C_{N+M}) 。
- 简介 C 为空。 如果
- A 和 B 都为空,则退出。 如果其中一个
- A 和 B 为空,则另一个序列为 t 。如果都不为空,则选择第一个元素较小的序列。 t 。然而, 当A 和 B 的第一个元素具有相同的值时, A 是 t 。
- t 的第一个元素 添加到 C 的末尾。 删除
- t 的第一个元素。
- 返回2。
广义单调递增正整数序列 给定 A, B ,该算法生成的正整数序列 创建一个输出 C 的程序。
制約
- 1 \leqq N \leqq 500.
- 1 \leqq M \leqq 500.
- 1 \leqq A_1 \leqq A_2 \leqq \cdots \leqq A_N \leqq 2000.
- 1 \leqq B_1 \leqq B_2 \leqq \cdots \leqq B_M \leqq 2000.
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 \cdots A_N B_1 B_2 \cdots B_M
出力
到标准输出 输出 N + M 行。 输出
k 行目 (1 \leqq k \leqq N + M)有C_k 。
入力例 1
2 1 1 2 2
出力例 1
1 2 2
在做算法之前,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) 。
入力例 2
3 8 1 3 8 3 3 4 5 6 7 8 9
出力例 2
1 3 3 3 4 5 6 7 8 8 9