310990: CF1918B. Minimize Inversions

B. Minimize Inversionstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given two permutations $a$ and $b$ of length $n$. A permutation is an array of $n$ elements from $1$ to $n$ where all elements are distinct. For example, an array [$2,1,3$] is a permutation, but [$0,1$] and [$1,3,1$] aren't.

You can (as many times as you want) choose two indices $i$ and $j$, then swap $a_i$ with $a_j$ and $b_i$ with $b_j$ simultaneously.

You hate inversions, so you want to minimize the total number of inversions in both permutations.

An inversion in a permutation $p$ is a pair of indices $(i, j)$ such that $i < j$ and $p_i > p_j$. For example, if $p=[3,1,4,2,5]$ then there are $3$ inversions in it (the pairs of indices are $(1,2)$, $(1,4)$ and $(3,4)$).

Input

The first line contains an integer $t$ ($1 \leq t \leq 20\,000$) — the number of test cases.

Each test case consists of three lines. The first line contains an integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the permutations $a$ and $b$. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — permutation $a$. The third line contains $b$ in a similar format.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

Output

For each test case, output two permutations $a'$ and $b'$ (in the same format as in the input) — the permutations after all operations. The total number of inversions in $a'$ and $b'$ should be the minimum possible among all pairs of permutations that can be obtained using operations from the statement.

If there are multiple solutions, print any of them.

ExampleInput

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

Output

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

Note

In the first test case, the minimum possible number of inversions is $10$.

In the second test case, we can sort both permutations at the same time. For this, the following operations can be done:

• Swap the elements in the positions $1$ and $3$ in both permutations. After the operation, $a =$ [$2,1,3$], $b =$ [$2,1,3$].
• Swap the elements in the positions $1$ and $2$. After the operations, $a$ and $b$ are sorted.

In the third test case, the minimum possible number of inversions is $7$.

题目大意：
这个题目是关于排列的最小逆序数问题。给定两个长度为n的排列a和b，排列是1到n的n个不同元素的数组。你可以任意次数选择两个索引i和j，然后同时交换a_i和a_j以及b_i和b_j。你希望最小化两个排列中逆序的总数。排列p中的一个逆序是一对索引(i, j)，满足i < j且p_i > p_j。输入包括t个测试用例，每个测试用例包括排列a和b的长度n和它们的元素。输出是对每个测试用例操作后的排列a'和b'，使得a'和b'的逆序数最小。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 20,000），表示测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含一个整数n（1 ≤ n ≤ 2·10^5），表示排列a和b的长度。
- 第二行包含n个整数a_1, a_2, ..., a_n（1 ≤ a_i ≤ n），表示排列a。
- 第三行以类似格式表示排列b。
- 保证所有测试用例的n之和不超过2·10^5。

输出：
- 对于每个测试用例，输出两行，分别表示操作后的排列a'和b'（格式与输入相同），使得a'和b'的逆序数最小。
- 如果有多个解决方案，输出其中任何一个。题目大意： 这个题目是关于排列的最小逆序数问题。给定两个长度为n的排列a和b，排列是1到n的n个不同元素的数组。你可以任意次数选择两个索引i和j，然后同时交换a_i和a_j以及b_i和b_j。你希望最小化两个排列中逆序的总数。排列p中的一个逆序是一对索引(i, j)，满足i < j且p_i > p_j。输入包括t个测试用例，每个测试用例包括排列a和b的长度n和它们的元素。输出是对每个测试用例操作后的排列a'和b'，使得a'和b'的逆序数最小。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 20,000），表示测试用例的数量。 - 每个测试用例包含三行： - 第一行包含一个整数n（1 ≤ n ≤ 2·10^5），表示排列a和b的长度。 - 第二行包含n个整数a_1, a_2, ..., a_n（1 ≤ a_i ≤ n），表示排列a。 - 第三行以类似格式表示排列b。 - 保证所有测试用例的n之和不超过2·10^5。 输出： - 对于每个测试用例，输出两行，分别表示操作后的排列a'和b'（格式与输入相同），使得a'和b'的逆序数最小。 - 如果有多个解决方案，输出其中任何一个。