AT_joi2020_yo1a_c マージ (Merge)

[problemUrl]: https://atcoder.jp/contests/joi2020yo1a/tasks/joi2020_yo1a_c 長さ $ 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 $ を出力するプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ 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\ \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 $． ### Sample Explanation 1 アルゴリズムを行う前，$ 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) $ である．