18410번 - マージ (Merge) 다국어

長さ N の正整数列 A=(A₁, A₂, ..., A_N) と，長さ M の正整数列 B=(B₁, B₂, ..., B_M) が与えられる． これらの数列は，共に広義単調増加数列である．つまり，A₁ ≦ A₂ ≦ … ≦ A_N, B₁ ≦ B₂ ≦ … ≦ B_M を満たす．

以下のアルゴリズムを用いて，これらの数列から，長さ N+M の正整数列 C=(C₁, C₂, ..., 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
A1 A2 … AN
B1 B2 … BM

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

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

• 1 ≦ N ≦ 500．
• 1 ≦ M ≦ 500．
• 1 ≦ A₁ ≦ A₂ ≦ … ≦ A_N ≦ 2000．
• 1 ≦ B₁ ≦ B₂ ≦ … ≦ B_M ≦ 2000．