eutral Tonality SOlution Codeforces

eutral Tonality SOlution Codeforces

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

Let LIS(c)LIS(�) denote the length of theof array c. For example, LIS([2,1,1,3])LIS([2,1_,1,3_]) = 22LIS([1,7,9])LIS([1_,7_,9_]) = 33LIS([3,1,2,4])LIS([3,1_,2_,4_]) = 33.

You need to insert the numbers b1,b2,,bm�1,�2,…,�� into the array a, at any positions, in any order. Let the resulting array be c1,c2,,cn+m�1,�2,…,��+�. You need to choose the positions for insertion in order to minimize LIS(c)LIS(�).

Formally, you need to find an array c1,c2,,cn+m�1,�2,…,��+� that simultaneously satisfies the following conditions:

  • The array a1,a2,,an�1,�2,…,�� is a subsequence of the array c1,c2,,cn+m�1,�2,…,��+�.
  • The array c1,c2,,cn+m�1,�2,…,��+� consists of the numbers a1,a2,,an,b1,b2,,bm�1,�2,…,��,�1,�2,…,��, possibly rearranged.
  • The value of LIS(c)LIS(�) is the minimum possible among all suitable arrays c.
Input

Each test contains multiple test cases. The first line contains a single integer t (1t104)(1≤�≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n,m�,� (1n2105,1m2105)(1≤�≤2⋅105,1≤�≤2⋅105) — the length of array a and the length of array b.

The second line of each test case contains n integers a1,a2,,an�1,�2,…,�� (1ai109)(1≤��≤109) — the elements of the array a.

The third line of each test case contains m integers b1,b2,,bm�1,�2,…,�� (1bi109)(1≤��≤109) — the elements of the array b.

It is guaranteed that the sum of n over all test cases does not exceed 21052⋅105, and the sum of m over all test cases does not exceed 21052⋅105.

Output

For each test case, output n+m�+� numbers — the elements of the final array c1,c2,,cn+m�1,�2,…,��+�, obtained after the insertion, such that the value of LIS(c)LIS(�) is minimized. If there are several answers, you can output any of them.

Example
input

Copy
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
output

Copy
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, LIS(a)=LIS([6,4])=1LIS(�)=LIS([6,4])=1. We can insert the number 55 between 66 and 44, then LIS(c)=LIS([6,5,4])=1LIS(�)=LIS([6,5,4])=1.

In the second test case, LIS([1,7,2,4,5])LIS([1_,7,2_,4_,5_]) = 44. After the insertion, c=[1,1,7,7,2,2,4,4,5,5]�=[1,1,7,7,2,2,4,4,5,5]. It is easy to see that LIS(c)=4LIS(�)=4. It can be shown that it is impossible to achieve LIS(c)LIS(�) less than 44.

 

Leave a Comment