Skip to content
Sign in

マージ (Merge)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

長さ \(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\) を出力するプログラムを作成せよ．

Constraints

  • \(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\)．

Input

入力は以下の形式で標準入力から与えられる．

\(N\) \(M\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(B_1\) \(B_2\) \(\cdots\) \(B_M\)

Output

標準出力に \(N + M\) 行出力せよ．

\(k\) 行目 (\(1 \leqq k \leqq N + M\)) には，\(C_k\) を出力せよ．

Examples

Sample input 1
2 1
1 2
2
Sample output 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)\) である．

Sample input 2
3 8
1 3 8
3 3 4 5 6 7 8 9
Sample output 2
1
3
3
3
4
5
6
7
8
8
9

Notes

JOI 2020 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source