B. Минимизируйте инверсии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две перестановки $$$a$$$ и $$$b$$$ длины $$$n$$$. Перестановкой называется массив из $$$n$$$ элементов от $$$1$$$ до $$$n$$$, в котором все элементы различны. К примеру, массив [$$$2,1,3$$$] является перестановкой, а [$$$0,1$$$] и [$$$1,3,1$$$] не являются.

Вы можете сколько угодно раз выбрать два индекса $$$i$$$ и $$$j$$$, а затем поменять местами элементы $$$a_i$$$ с $$$a_j$$$ и $$$b_i$$$ с $$$b_j$$$ одновременно.

Вы ненавидите инверсии и поэтому хотите минимизировать суммарное число инверсий в обеих перестановках.

Инверсией в перестановке $$$p$$$ называется пара индексов $$$(i, j)$$$, такая что $$$i < j$$$ и $$$p_i > p_j$$$. Например, если $$$p=[3,1,4,2,5]$$$, то количество инверсий в этой перестановке равно $$$3$$$ (искомые пары индексов: $$$(1,2)$$$, $$$(1,4)$$$ и $$$(3,4)$$$).

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

В первой строке входных данных вводится одно число $$$t$$$ ($$$1 \leq t \leq 20\,000$$$) — количество запросов.

Каждый набор входных данных состоит из трех строк. В первой строке вводится число $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — длина перестановок $$$a$$$ и $$$b$$$. Во второй строке вводится $$$n$$$ элементов $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — перестановка $$$a$$$. В третьей строке в аналогичном формате вводится перестановка $$$b$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot10^5$$$.

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

Для каждого набора входных данных выведите две перестановки $$$a'$$$ и $$$b'$$$ — перестановки после применения операций. Суммарное количество инверсий в $$$a'$$$ и $$$b'$$$ должно быть минимально возможным среди всех пар перестановок, которые возможно получить с помощью операций из условия.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
3
5
1 2 3 4 5
5 4 3 2 1
3
3 1 2
3 1 2
6
2 5 6 1 3 4
1 5 3 6 2 4
Выходные данные
3 2 5 1 4
3 4 1 5 2
1 2 3
1 2 3
2 3 4 6 5 1
1 2 4 3 5 6
Примечание

В первом тесте минимальное достижимое количество инверсий равно $$$10$$$.

Во втором наборе входных данных можно отсортировать обе перестановки одновременно. Для этого можно применить следующие операции:

  • Поменять элементы на позициях $$$1$$$ и $$$3$$$ в обеих перестановках. После операции $$$a =$$$ [$$$2,1,3$$$], $$$b =$$$ [$$$2,1,3$$$].
  • Поменять элементы на позициях $$$1$$$ и $$$2$$$. После операции $$$a$$$ и $$$b$$$ отсортированы.

В третьем тесте минимальное достижимое количество инверсий равно $$$7$$$.