题目描述

给定两个长度分别为 $n$ 和 $m$ 的有序（非降序）数组 $a$ 和 $b$。

请你将这两个数组合并成一个新的数组，并要求合并后的数组依然保持有序（非降序）。

输入格式

第一行包含两个正整数 $n$ 和 $m$ —— 分别表示数组 $a$ 和数组 $b$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 表示有序数组 $a$ 的元素。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ —— 表示有序数组 $b$ 的元素。

输出格式

输出一行，包含 $n+m$ 个整数，表示合并后的有序数组。相邻两个整数之间用一个空格隔开。

样例输入 1

3 4
1 3 5
2 4 6 8

样例输出 1

1 2 3 4 5 6 8

样例输入 2

4 3
2 2 3 9
1 2 5

样例输出 2

1 2 2 2 3 5 9

说明

样例解释

在第一个样例中，数组 $a$ 为 $[1, 3, 5]$，数组 $b$ 为 $[2, 4, 6, 8]$。将它们合并并排序后，得到的数组为 $[1, 2, 3, 4, 5, 6, 8]$。

数据范围

对于所有测试点，保证：

• $1 \le n, m \le 10^6$。
• $1 \le a_i, b_i \le 10^9$。
• 保证给定的数组 $a$ 和 $b$ 本身已经是升序（非降序）排列，即 $a_1 \le a_2 \le \dots \le a_n$ 且 $b_1 \le b_2 \le \dots \le b_m$。