Codeforces Round 908 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

data structures

sortings

two pointers

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Neutral Tonality

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard 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$$$.

Input

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$$$.

Output

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.

Example

Input

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

Output

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

Note

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$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2024 22:24:56 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|