CF1893B.Neutral Tonality

You are given an array $a$ consisting of $n$ integers, as well as an array $b$ consisting of $m$ integers.

Let $\text{LIS}(c)$ denote the length of the longest increasing subsequence of array $c$. For example, $\text{LIS}([2, \underline{1}, 1, \underline{3}])$ = $2$, $\text{LIS}([\underline{1}, \underline{7}, \underline{9}])$ = $3$, $\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])$ = $3$.

You need to insert the numbers $b_1, b_2, \ldots, b_m$ into the array $a$, at any positions, in any order. Let the resulting array be $c_1, c_2, \ldots, c_{n+m}$. You need to choose the positions for insertion in order to minimize $\text{LIS}(c)$.

Formally, you need to find an array $c_1, c_2, \ldots, c_{n+m}$ that simultaneously satisfies the following conditions:

• The array $a_1, a_2, \ldots, a_n$ is a subsequence of the array $c_1, c_2, \ldots, c_{n+m}$.
• The array $c_1, c_2, \ldots, c_{n+m}$ consists of the numbers $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_m$, possibly rearranged.
• The value of $\text{LIS}(c)$ is the minimum possible among all suitable arrays $c$.

给你一个由 $n$ 个整数组成的数组 $a$，以及一个由 $m$ 个整数组成的数组 $b$。

记 $\text{LIS}(c)$ 为数组 $c$ 的最长递增子序列 的长度。例如，$\text{LIS}([2, \underline{1}, 1, \underline{3}]) = 2$，$\text{LIS}([\underline{1}, \underline{7}, \underline{9}]) = 3$，$\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}]) = 3$。

你需要将数字 $b_1, b_2, \ldots, b_m$ 插入到数组 $a$ 中（可插在任意位置，顺序可任意）。设得到的数组为 $c_1, c_2, \ldots, c_{n+m}$。你需要选择插入位置，使得 $\text{LIS}(c)$ 尽可能小。

形式化地说，你需要找到一个数组 $c_1, c_2, \ldots, c_{n+m}$，使其同时满足以下条件：

• 数组 $a_1, a_2, \ldots, a_n$ 是数组 $c_1, c_2, \ldots, c_{n+m}$ 的一个子序列；
• 数组 $c_1, c_2, \ldots, c_{n+m}$ 由数字 $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_m$ 组成（顺序可重排）；
• 在所有满足上述条件的数组 $c$ 中，$\text{LIS}(c)$ 的值最小。

Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 10^4)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n, m$ $(1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$ — the length of array $a$ and the length of array $b$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^9)$ — the elements of the array $a$.

The third line of each test case contains $m$ integers $b_1, b_2, \ldots, b_m$ $(1 \leq b_i \leq 10^9)$ — the elements of the array $b$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$, and the sum of $m$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$ $(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$ 的长度和数组 $b$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $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$。

For each test case, output $n + m$ numbers — the elements of the final array $c_1, c_2, \ldots, c_{n+m}$, obtained after the insertion, such that the value of $\text{LIS}(c)$ is minimized. If there are several answers, you can output any of them.

对于每个测试用例，输出 $n + m$ 个数——即插入操作后得到的最终数组 $c_1, c_2, \ldots, c_{n+m}$ 的元素，使得 $\text{LIS}(c)$ 的值最小。如果存在多个满足条件的答案，输出任意一个即可。

In the first test case, $\text{LIS}(a) = \text{LIS}([6, 4]) = 1$. We can insert the number $5$ between $6$ and $4$, then $\text{LIS}(c) = \text{LIS}([6, 5, 4]) = 1$.

In the second test case, $\text{LIS}([\underline{1}, 7, \underline{2}, \underline{4}, \underline{5}])$ = $4$. After the insertion, $c = [1, 1, 7, 7, 2, 2, 4, 4, 5, 5]$. It is easy to see that $\text{LIS}(c) = 4$. It can be shown that it is impossible to achieve $\text{LIS}(c)$ less than $4$.

在第一个测试用例中，$\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$。