B. Нейтральная тональность
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых положительных чисел, а также массив $$$b$$$ из $$$m$$$ целых положительных чисел.

Пусть $$$\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$$$, возможно, переставленных в другом порядке.
  • Значение $$$\text{LIS}(c)$$$ минимально возможное среди всех подходящих массивов $$$c$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите $$$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$$$. Можно вставить число $$$5$$$ между $$$6$$$ и $$$4$$$, тогда $$$\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$$$, добиться невозможно.