← 返回题目列表

AtCoder · joi2020_yo1a_c

C. 合并

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

配点: 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}) 。

  1. 简介 C 为空。 如果
  2. A 和 B 都为空,则退出。 如果其中一个
  3. A 和 B 为空,则另一个序列为 t 。如果都不为空,则选择第一个元素较小的序列。 t 。然而, 当A 和 B 的第一个元素具有相同的值时, A 是 t 。
  4. t 的第一个元素 添加到 C 的末尾。 删除
  5. t 的第一个元素。
  6. 返回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