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.

힌트