该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给您两个长度为 $n$ 的排列 $a$ 和 $b$ 。排列是从 $1$ 到 $n$ 的 $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$ 。