该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定两个序列 $a,b$，将 $b$ 中所有元素以任意顺序在任意位置插入 $a$ 中，使得形成的新序列 $c$ 的最长上升子序列最短，输出你的序列 $c$。

输入描述

每个测试包含多个测试用例。第一行包含一个整数 $t$ $(1 \leq t \leq 10^4)$ - 测试用例数。 $(1 \leq t \leq 10^4)$ - 测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n, m$ $(1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$ - 数组 $a$ 的长度和数组 $a$ 的长度。 $(1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$ -数组 $a$ 的长度和数组 $b$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^9)$ - 数组 $a_1, a_2, \ldots, a_n$ 的元素。 $(1 \leq a_i \leq 10^9)$ -数组 $a$ 的元素。

每个测试用例的第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$ 。 $(1 \leq b_i \leq 10^9)$ - 数组 $b$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$ ，所有测试用例的 $m$ 之和不超过 $2\cdot 10^5$ 。

输出描述

对于每个测试用例，输出 $n + m$ 个数字--插入后得到的最终数组 $c_1, c_2, \ldots, c_{n+m}$ 中的元素，使得 $\text{LIS}(c)$ 的值最小。如果有多个答案，可以输出任意一个。

7
2 1
6 4
5
5 5
1 7 2 4 5
5 4 1 2 7
1 9
7
1 2 3 4 5 6 7 8 9
3 2
1 3 5
2 4
10 5
1 9 2 3 8 1 4 7 2 9
7 8 5 4 6
2 1
2 2
1
6 1
1 1 1 1 1 1
777

6 5 4
1 1 7 7 2 2 4 4 5 5
9 8 7 7 6 5 4 3 2 1
1 3 5 2 4
1 9 2 3 8 8 1 4 4 7 7 2 9 6 5
2 2 1
777 1 1 1 1 1 1

说明

在第一个测试用例 $\text{LIS}(a) = \text{LIS}([6, 4]) = 1$ 中。我们可以在 $6$ 和 $4$ 之间插入数字 $5$ ，然后是 $\text{LIS}(c) = \text{LIS}([6, 5, 4]) = 1$ 。

在第二个测试用例中， $\text{LIS}([\underline{1}, 7, \underline{2}, \underline{4}, \underline{5}])$ = $4$ 。插入后为 $c = [1, 1, 7, 7, 2, 2, 4, 4, 5, 5]$ 。不难看出， $\text{LIS}(c) = 4$ .由此可见， $\text{LIS}(c)$ 不可能小于 $4$ 。