B. Neutral Tonalitytime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou 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.InputEach 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.OutputFor 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.ExampleInput
72 16 455 51 7 2 4 55 4 1 2 71 971 2 3 4 5 6 7 8 93 21 3 52 410 51 9 2 3 8 1 4 7 2 97 8 5 4 62 12 216 11 1 1 1 1 1777Output
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
NoteIn 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.
72 16 455 51 7 2 4 55 4 1 2 71 971 2 3 4 5 6 7 8 93 21 3 52 410 51 9 2 3 8 1 4 7 2 97 8 5 4 62 12 216 11 1 1 1 1 1777
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 
['constructive algorithms', 'greedy', 'sortings', 'two pointers', '*1700']