001 - マージ

時間制限 2 秒 / メモリ制限 1024 MB / 得点 100 / x 5 /


TLE
2sec
MLE
1024MB
得点
100

問題文

長さ N の正整数列 A=(A1, A2, ..., AN) と,長さ M の正整数列 B=(B1, B2, ..., BM) が与えられる. これらの数列は,共に広義単調増加数列である.つまり,A1 ≦ A2 ≦ … ≦ AN, B1 ≦ B2 ≦ … ≦ BM を満たす.

以下のアルゴリズムを用いて,これらの数列から,長さ N+M の正整数列 C=(C1, C2, ..., CN+M) を生成する.

  1. はじめ C は空とする.
  2. AB がどちらも空の場合,終了する.
  3. AB のどちらかが空の場合,そうでない数列を t とおく.どちらも空でない場合,先頭の要素が小さい数列を t とおく.ただし,AB の先頭の要素が同じ値のときは At とおく.
  4. t の先頭の要素を C の末尾に追加する.
  5. t の先頭の要素を削除する.
  6. 2. に戻る.

広義単調増加な正整数列 A, B が与えられたとき,このアルゴリズムにより生成される正整数列 C を出力するプログラムを作成せよ.

制約

  • 1 ≦ N ≦ 500
  • 1 ≦ M ≦ 500
  • 1 ≦ A1 ≦ A2 ≦ … ≦ AN ≦ 2000
  • 1 ≦ B1 ≦ B2 ≦ … ≦ BM ≦ 2000

入力

入力は以下の形式で標準入力から与えられる.
N M
A1 A2 AN
B1 B2 BM

出力

標準出力に N + M 行出力せよ.
k 行目 (1 ≦ k ≦ N + M) には,Ck を出力せよ.

入出力例

入力例 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